# 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)

Now if the adversary can additionally compromise all but the sending and the receiving user in some specific time interval, then the adversary can naturally relate sender and receiver. The question in such a at least two Mix setting is how large the remaining anonymity set (set of non-compromised users) stays and how flexible your attackers is.

But with all those anonymous communication systems there are many known issues in the real world with traffic analysis, since you have no constant message flow and the message exchanges between any two parties are biased. There are countermeasures such as dummy traffic, etc. but it is questionable if this is really practical. This paper provides a nice overview of various types of attacks. For low latency services (such as email) one can apply a strategy to collect a bunch of messages (threshold or pool mixing) and only send them if enough are available (after mixing and padding to the same size such that there is no correlation of input and output).

I am not sure if this really answers your question, but just comment and I will edit (if I can provide more meaningful info).

-
It is possible to let a third client Carol act as a mix. Sue is however the only entity that all parties are able reach directly (i.e. the only one with a static IP or registered DNS name). The routing could e.g. be: Alice->Sue->Carol->Sue->David->Sue->Bob. –  Henrick Hellström Dec 19 '13 at 3:48
You mean that Sue collects the messages, sends them to Carol for mixing and then Sue receives back the "mixed" messages? If the attacker compromises Sue this will not give you any benefit, since I assume that Sue knows senders and receivers of all messages (if you want to avoid that all users need to download all the messages all the time). As said in the answer, using two parties acting as mixes eliminates this problem assuming that not both parties get compromised at the same time. –  DrLecter Dec 19 '13 at 10:38
I wasn't clear. With such a solution Alice would of course have to send a message with layered encryption. When Sue has peeled off the first layer, all that it says is that the message is intended for Carol, etc. Obviously, if the first mixer sees the final recipient, Eve will just have to compromise the first mixer to get the actual traffic data. –  Henrick Hellström Dec 19 '13 at 10:53
Ah ok, yes that should work out assuming that Sue and Carol are not compromised at the same time. –  DrLecter Dec 19 '13 at 11:01
I think your answer summarizes the (publicly known) state of the art of traffic analysis counter measures, but I am holding my accept to see if there are any other takers. –  Henrick Hellström Dec 21 '13 at 11:22