# Private Messaging

Suppose Alice and Bob wants to send messages through Sue without revealing to Eve that the exchange took place. Slightly more formally, I don't want Eve to have any advantage telling if Alice is sending spam to random recipients, or if Alice is engaged in an information exchange with Bob. Is this possible?

Eve tracks all communications to and from Sue, and might at any time get any internal information from Sue, except the private key of Sue.

There are other users sending messages through Sue, besides Alice and Bob, and Eve might at any time compromise any one of those users, but not all of them at once, to see what information that user is receiving, and from whom.

For clarity, an ideal solution would be if Alice and Bob use public key encryption, without adding any identifiers to the messages. Sue maintains only a single mailbox, so each user simply downloads all messages for all users. Bob knows which messages are intended for him, because those messages are the only ones he is able to decrypt. However, this would get impractical quickly as the number of users grow, but on the other hand would still require a fairly high number of users to be secure.

I have considered variations of onion/tor routing, but fail to see how this could be made secure given the requirement and the threat scenario: If completely random routing is used, the intended recipient will stick out in the noise of the total traffic generated each time Alice sends a message. If only a few infrequently rotated routing trees are used for each recipient, Eve might compromise the other users in those routing trees and track the layers of the message that eventually reaches Bob.

• There are two recent works that I am aware of that could be useful to your approach: It's this paper from CCS (were you also find other related work) and this paper from PETS. – DrLecter Dec 18 '13 at 8:11
• @DrLecter: Am I correct that those papers deal with the details of the "ideal" solution I outlined, and hence suffer from an overhead that is linear in either the number of users or the total number of messages? – Henrick Hellström Dec 18 '13 at 11:25
• The first paper from CCS is about encryption schemes that produce ciphertext that are not distinguishable from random strings. The second paper deals with receiver anonymity in public key encryption schemes. But to be honest, I did not study them in detail yet. – DrLecter Dec 18 '13 at 11:27

After reading your question again, I think that a MIX net with at least two mixes may solve your problem. Onion routing (in particular Tor as an implementation of its second generation) is designed for low latency services, such as web browsing. Another approach for services which tolerate high latency (such as email) is for instance mixminion. Typically, it is easier to realize anonymity for low latency services as traffic analysis gets harder. Here is a nice survey article by George Danezis and Claudia Diaz on various approaches.

So in the following we assume that messages $m$ are encrypted under recipients public keys (giving $c$) and additionally together with the address $R$ of the recipient, i.e., $(c,R)$ under the public key of Sue. Consequently, an adversary not compromising Sue will have no idea of the message is random garbage or a meaningful message. More on this below.

Compromising Sue(s)