Mike Ingle writes: [...]
Anonymity needs something fundamentally new, something comparable to public key for cryptography or blind signatures for digital cash. Suppose a server has a large file. A message comes in and is combined into this file. Another message comes in with a key to retrieve data. The server processes the retrieval key against this large file and comes up with an output, which it returns to the person doing the retrieving. This output contains the input message, transformed in such a way that even the server cannot match it to the input that produced it. This is what we need. [...]
In a naive model, the sender could encrypt the message with two distinct public keys belonging to the intended recipient. The server shuffles the result randomly with all its other messages. The recipient sends the private key associated with the outer layer of encryption to the server, which in turn finds something to decrypt with that key. Finally the recipient receives the singly-encrypted message, and uses her other private key to decipher the message. This still places full trust in the server, though. It's trivial for the server to log each incoming message separately, noting the sender, in addition to combining it with the melange of all received traffic as expected. Thus the protocol above fails, since the server can simply test-decrypt each distinct original file with the private key supplied by the intended recipient, thereby linking the ends of the communication. So the function computed on the melange file and the recipient-supplied key must not do anything extraordinary when applied to the original message and the recipient key. Actually, it's much worse than that. The server could create a mock melange file, combine each original message with it, then apply the extraction function to each resulting melange and the recipient key. Since the recipient has no control over the previous state of the melange file, prior to the arrival of the message for her, the extraction function can't depend in any detailed way upon the contents of the melange. Therefore, I believe it's impossible to specify an extraction function immune to melange spoofing by the server. -L. Futplex McCarthy, seeking summer employment in computer science; background mainly in theoretical CS, but open to many alternatives [private email please]