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.

  • $\begingroup$ 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. $\endgroup$
    – DrLecter
    Commented Dec 18, 2013 at 8:11
  • $\begingroup$ @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? $\endgroup$ Commented Dec 18, 2013 at 11:25
  • $\begingroup$ 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. $\endgroup$
    – DrLecter
    Commented Dec 18, 2013 at 11:27

1 Answer 1


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.

Now to your scenario:

Compromising Sue(s)

Clearly, if you have only one mix (Sue) and this one gets compromised, then any adversary can relate senders and receivers when having full access to Sue (although the adversary cannot read the messages when they are public key encrypted under the respective recipients public key. Furthermore, when using a Mix net we assume that these ciphertexts are additionally encrypted under Sues public key to hide the recipients address from eavesdroppers). Note that even if the adversary has no access to Sues private key but has full access to Sue the adversary can related incoming and outgoing messages. However, if you have at least two Mixes (assume we have exactly two for simplicity), where not both can get compromised at the same time, then the adversary can either determine the senders or the receivers in one time interval, but not both at the same time, consequently not being able to link senders to receivers.

Compromising senders and receivers

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

  • $\begingroup$ 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. $\endgroup$ Commented Dec 19, 2013 at 3:48
  • $\begingroup$ 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. $\endgroup$
    – DrLecter
    Commented Dec 19, 2013 at 10:38
  • $\begingroup$ 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. $\endgroup$ Commented Dec 19, 2013 at 10:53
  • $\begingroup$ Ah ok, yes that should work out assuming that Sue and Carol are not compromised at the same time. $\endgroup$
    – DrLecter
    Commented Dec 19, 2013 at 11:01
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Dec 21, 2013 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.