Re: New directions in anonymity (needed)

["L. McCarthy" <lmccarth@ducie.cs.umass.edu>]

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]