On Fri, 6 Oct 2000, despot wrote:
But, this disposable remailer idea is solid. As a quick example scheme, if there were some sort of remailer protocol that functioned like routing protocols, as disposable remailers came online, they could announce themselves to other remailers. Pseudorandom hopping from one disposable remailer to another could occur in a remailer-chained message, instead of manually encrypting a message for a chain of remailers. The sender could
This reminds me of something I was looking at this spring. Markus Jakobsson has two papers on "A Practical Mix" and "Flash Mixing" which look at mix-nets in a different way than we see in remailers. There, instead of a message being successively encrypted for a particular path through a series of remailers, the remailers pass a prepared encrypted message around and perform a distributed computation on it. At the end of the computation, the decrypted name of the recipient automagically pops out. These kinds of remailers are not original to Jakobsson - but previous efforts that I know about are ridiculously inefficient. The number I remember for one of them is 1600 modexps per message per server. Jakobsson's "Practical Mix" proposal is more like 160. The "Flash Mixing" paper investigates ways to use precomputation to get this to 160 multiplications. I should mention here that Yvo Desmedt and Karou Kurosawa showed in Eurocrypt 2K that the original "Practical Mix" paper has a flaw -- an evil node can cause one of the distributed computations to abort without being caught. They noted that their results didn't extend to the "Flash Mixing" paper; it's been a back-burner project of mine to look at this for...well...too long. Anyway, both papers deal with a collection of mix servers fixed in advance. It seems that disposable remailers would work well with extensions of these protocols modified to deal with dynamic leave and joins of servers. Add this to wireless and you have mobile disposable remailers. Slightly related would be the idea of using commodity computation to do remailing -- just tell people to "go to this page, download this applet, become a remailer!" (or have your HD erased, but...) There are massive issues with trusting new remailer nodes, unfortunately. Imagine what happens when your adversary decides to show up with polynomially many of her closest friends. So a further question would be whether we can design a mix protocol which can a) take advantage of all these cheap, (hopefully) distinct devices and their computation power but b) doesn't give the commodity devices enough power to break the mix, even if many (almost all??) of them act in concert.
On a side note, what other throw-away internet-ready devices would be of interest? Motion detectors? Access control devices? Door locks?
Pretty much everything, if you believe some people. The Oxygen project at MIT has a vision of computation in absolutely everything. Desmedt has an intriguing article about just what might happen then.. -David