Provable Unlinkability Against Traffic Analysis with Low Message Overhead

Rackoff and Simon proved that a variant of Chaum's protocol for anonymous communication, later developed as the Onion Routing Protocol, is unlinkable against a passive adversary that controls all communication links and most of the nodes in a communication system. A major drawback of their analysis is that the protocol is secure only if (almost) all nodes participate at all times. That is, even if only n?N nodes wish to send messages, allN nodes have to participate in the protocol at all times. This suggests necessity of sending dummy messages and a high message overhead. Our first contribution is showing that this is unnecessary. We relax the adversary model and assume that the adversary only controls a certain fraction of the communication links in the communication network. We think this is a realistic adversary model. For this adversary model we show that a low message overhead variant of Chaum's protocol is provably secure. Furthermore, all previous security proofs assumed the a priori distribution on the messages is uniform. We feel this assumption is unrealistic. The analysis we give holds for any a priori information on the communication distribution. We achieve that by combining Markov chain techniques together with information theory tools in a simple and elegant way.