On Fri, 6 Oct 2000, dmolnar wrote:

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

path through a series of remailers, the remailers pass a

I will inject one missing piece of my example, the final remailer address (and perhaps even the whole message) should be obfuscated by the hop count. This way only the last disposable remailer before the final remailer has this information. particular 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.

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.

So a further question would be whether we can design a mix

Ok, I am stretching my memory here, but... I read about mix-nets and the "Flash Mixing" paper months ago, so I may be a bit off. If I remember correctly, you have network of mix servers. Any set of these mix servers can be used to perform the mix, and as long as one is "honest," the result will be private. These servers communicate over some sort of broadcast channel. Lets say C is a list of the ciphertexts (c0...ci) after encrypting messages M (m0...mi) with a public key. C flows through the mix-net where it is re-encrypted, permuted, sorted, etc by each mix server (so each mix server has a modified copy of the list) and out pops C'. C' is a list of ciphertexts corresponding to M. For the Flash Mix, the mix servers can confirm to a high probability that C' was computed correctly. As long as one of the mix servers is honest and an attacker does not know, I think it is, 2 plaintexts corresponding to input ciphertexts, then there is a high probability of privacy. More so, I believe there are even dummy inputs in the list C to help strengthen this scheme against attacks. So, off the top of my head, issues with extending this scheme to disposable remailers... Well, the list size immediately comes to mind for memory-constrained devices. The resistance to attack is dependent on the list size and the number of lists (which corresponds to the number of mix servers used). Adding nodes should have no impact as they would not be part of the current mixes. Dropping nodes not used in any mixes would be fine, but what happens when a node being used in a mix fails? The mix could start over, using pseudorandomly selected nodes perhaps. The system also seems to fall prey to malicious remailers. For the flash mix, I believe, it is assumed that nodes will perform properly more often than not, but this seems to be the rarer case in a disposable remailer structure. The means of communication would need to be looked at, especially with this dynamic environment. How to eliminate nodes that are found to be malfunctioning from being used by other nodes? A few trusted, "honest" nodes should be available to the mixes in order to ensure privacy. And so on... :) 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.

Indeed... -andrew