This work investigates the fundamental constraints of anonymous communication (AC) protocols. We analyze the relationship between bandwidth overhead, latency overhead, and sender anonymity or recipient anonymity against the global passive (network-level) adversary. We confirm the trilemma that an AC protocol can only achieve two out of the following three properties: strong anonymity (i.e., anonymity up to a negligible chance), low bandwidth overhead, and low latency overhead.
Millions of users from all over the world employ anonymous communication networks, such as Tor, to protect their privacy over the Internet. The design choice made by the Tor network to keep the latency and bandwidth overheads small has made it highly attractive to its geographically diverse user-base. However, over the last decade, the academic literature has demonstrated Tor’s vulnerability to a variety of traffic correlation attacks. In fact, Tor also has been successfully attacked in practice.
It is widely accepted that low-latency low-bandwidth overhead of anonymous communication (AC) protocols, such as Tor, can only provide a weak form of anonymity. In the anonymity literature, several AC protocols were able to overcome this security barrier to provide a stronger anonymity guarantee (cryptographic indistinguishability based anonymity) by either increasing the latency overhead or the bandwidth overhead. In particular, high-latency approaches (such as threshold mix networks) can ensure strong anonymity by introducing significant communication delays for users messages, while high-bandwidth approaches (such as Dining Cryptographers network and its extensions) can provide strong anonymity by adding copious noise (or dummy) messages.
There have been a few efforts to propose hybrid approaches that try to provide anonymity by simultaneously introducing latency and bandwidth overhead. However, it is not clear how to balance such system parameters to ensure strong anonymity while preserving practical performance.
In general, in the last 35 years a significant amount of research efforts have been put towards constructing novel AC protocols, deploying them, and attacking real-world AC networks. However, unlike other security fields such as cryptography, our understanding regarding the fundamental limits and requirements of AC protocols remains limited. This work takes some important steps towards answering fundamental question associated with anonymous communication. “Can we prove that strong anonymity cannot be achieved without introducing large latency or bandwidth overhead? When we wish to introduce the latency and bandwidth overheads simultaneously, do we know the overhead range values that still fall short at providing stronger anonymity?”
The fourth factor: The analysis of AC protocol remains incomplete without a user description, i.e. , the pattern/frequency at which the AC protocol receives the input messages. For example, if the protocol receives a million of messages within an interval of 1 millisecond, it's easy for the protocol to provide high anonymity with a maximum delay 1 ms for any message. On the contrary, if the protocol receives only a few messages per second, it will be really difficult for the AC protocol to provide anonymity even with a delay of 1 second for each message.
We analyze two different user distributions: (i) synchronized user distributions, where users globally synchronize their messages, and (ii) unsynchronized user distributions, where each user locally decides when to send his messages independent of other users. For each of the user distributions, we derive upper bounds on sender anonymity as functions of bandwidth overhead and latency overhead, against two prominent adversary classes: global passive network-level adversaries and strictly stronger adversaries that additionally (passively) compromise some protocol parties (e.g., relays in case of Tor). These bounds constitute necessary constraints for anonymity. Naturally, the constraints are valid against any stronger adversary class as well. The results for recipient anonymity are also similar, with a difference of a constant multiplicative factor.