Please find below a summary of the lectures given on day #2 of the Interdisciplinary Summerschool on Privacy (ISP 2016), held at Berg en Dal this week. There was a lecture by George Danezis on anonymous communication.
All current networking protocols emanate information about the communication (i.e the meta data) all the time: the identity of the sender, the receiver, the length, the site you visit, and more. Anyone observing the network can see this.
How can you build networks that do not have this 'leaky' behaviour, and that protect the meta data (as well as the content) of the communication between Alice and Bob?
We want anonymity for two types of reasons. The first are internal to specific applications, like electronic voting, auctions, incident reporting, etc. The others are more general: protecting freedom of speech, prevent profiling, censorship resistance, etc.
Properties you want: sender anonymity (for example when a whistle blower wants to contact a journalist without revealing his own identity), receiver anonymity (for example when the journalist that was contacted anonymously by a whistle blower may want to ask for clarifications, without needing to know who the whistle blower is), bi-directional anonymity (combining both properties). Note that a simple broadcast channel (think TV or radio) provides receiver anonymity. This does not provide sender anonymity. Moreover, the amount of anonymity provided by a broadcast is the size of the audience that is a potential receiver. This teaches an important messages: to build anonymous system you need to construct a large crowd to hide in.
A weaker form of guarantee is third party anonymity that only provides the above properties only for external, third, parties: Alice and Bob themselves are allowed to know whom they are communicating with. This weaker form is what we really should expect of any future network technology.
Finally there is unobservability, that guarantees that no one can tell whether (this is a property that you want to hold for a platform that is only used for whistle blowing, because in this case the mere fact that you are participating is very sensitive).
To achieve sender anonymity is more work. The first solution of this problem is due to David Chaum, and he called it the Dining Cryptographers protocol. (I'm not replicating the solution here; it is documented well elsewhere.) Dining Cryptographers networks offer perfect anonymity, however the communication cost is bad (you need to use a broadcast for every message that needs to be send, and for every possible sender).
However "in the long run we are all dead" (Keynes). This also applies to anonymity. Even if a system offers perfect anonymity, in the long run an adversary analyzing all traffic over a prolonged period of time will be able to deduce information. This is because in real life each participant has a particular profile: Alice sends only at certain times (in the morning) and only to certain people (friends, colleagues). Hence, people receiving messages in the morning are more likely to be a friend or colleague of Alice. In this sense the protection offered by anonymity systems is much less strong (by nature) than normal encryption. In other words: the content of the messages can be protected in a much stronger way than the meta data. This makes anonymity, according to George, a 'tactical' property (in the sense it is only useful for a short time but cannot be maintained for a long time).
Another way to implement anonymous communication is mix networks, like Tor. (Again I'm not replicating the solution here; this is also documented well elsewhere).
Traditional mix systems delay messages (to provide anonymity); Tor doesn't, which makes it usable for anonymous web surfing. But this also makes it more vulnerable to traffic analysis. Tracing attacks (that match the timings of an incoming packet stream entering the Tor network with an outgoing packet stream leaving the Tor network) allow senders and receivers to be linked. This requires a global passive adversary (that can observe the whole network, like maybe the NSA can - George says this is not so clear...).
Future directions in onion routing (a particular type of mix networking). History is on our side when building anonymous communications. Network become faster and traffic becomes cheaper. We can use this to build more secure anonymous networks, for example by letting all users send fixed network packets every time slot.