Recipient Anonymity

[ghio@temp0097.myriad.ml.org (Matthew Ghio)]

A group of servers collects messages of equal length for anonymous
recipients.  All servers exchange messages so that each has copies of all
messages.

A recipient wishes to retrieve a message from the servers without any
server knowing which message he is receiving.  The recipient selects a
group of n servers.  From each server, S_1...S_n-1, he requests a random
selection of messages, with a 50% probability that any particular message
will be selected.  The server returns the xor of all messages requested.
He sends the final server a request which is the xor of all the previous
requests and the one single message that he wants.

The xor of all the responses is the desired message.  It is impossible to
determine which message was received unless all servers collude.

A variant of this scheme where there is only one server and a number of
anonymizing proxies will also work, however in this case there must be
sufficient delay to obscure the time correlations or the server will know
which message was received, and collusion with any one of the proxies
could reveal the recipient.

It is also possible to eliminate the need for real-time communication and
operate the system on a store-and-forward network.  The recipient
generates a one time pad and sends it to a remailer/messageserver along
with a reply-block which is a nested series of encrypted message requests
and next-hop addresses.  Each remailer along the way xors the requested
messages onto the existing message data before forwarding it to the next
hop.  When the recipient gets his message back, he decrypts it using the
one time pad.  To account for the situation where first and last remailer
collude, it is desireable to have some of the intervening remailers apply
a stream cipher to the message using a supplied key.

The server-to-server broadcast eliminates the need for cover traffic, but
the anonymizing proxy system does not.  However, there is no reason that
both schemes could not be used concurrently in the same network, and in
fact they would look the same to the end-user.

Except for the additional server-to-server communications necessary to
broadcast new messages into the system, the bandwidth utilization is
comparable to sender-anonymous remailers; it scales linearly as the
number of parties involved in the delivery of a particular message.  The
failure rate is also the product of the failure rate for each server; if
one server delivers corrupt data, the message is unreadable, and the
recipient must identify the bad server and eliminate it from future
requests.