Anonymity Trilemma
Strong Anonymity, Low Bandwidth Overhead, Low Latency — Choose Two.
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.
Our model captures all AC protocols under the assumption that messages are transmitted directly, i.e., in order for Bob to receive a message from Alice, Alice has to send the message and the message (albeit relayed, delayed and cryptographically modified) eventually has to reach Bob. This class of protocols characterize mainly mix-nets (including onion routing); as well as DC-nets given that there is no out-of-band coordination among usrs or a separate setup phase. Read the full paper here.
Synchromized User Distribution with Non-compromising Adversaries
Synchromized User Distribution with Compromising Adversaries
Unsynchromized User Distribution with Non-compromising Adversaries
Unsynchromized User Distribution with Compromising Adversaries
We now extend our impossibility results for protocols that has some kind of out-of-band coordination among users or a separate setup phase, along with all the tricks of mix-nets. We call this wider class of protocols as user description. In this class of protocols we identify a property that is reminiscent of secret sharing protocols: assuming some form of synchronization among protocol protocol parties, even the recipients of a message cannot distinguish the packet sent by the real sender and the dummy messages. As an example, secret-sharing a real message offline among several protocol parties and then sending the shares at a pre-agreed time, would achieve this property, since the content of the message would be shared among all messages and would not solely be contained in the message of the real sender. Alternatively, DC-nets shared keys to produce dummy messages that are needed to reconstruct the original message, which also achieves our proposed property.
We abstract away from how ACNs would synchronize and solely analyze the core of a secret-sharing based ACN: for this core we prove a necessary relationship between bandwidth, latency, and the degree of anonymity in the presence of compromised parties. In particular, for ACNs that can perform the above-mentioned synchronization offline, our novel necessary constraints give lower bounds on the bandwidth overhead for ACNs with low latency and strong anonymity in the presence of compromised parties. Our results thereby points future research on designing optimal ACNs in the direction of secretsharing based ACNs.
We indeed prove the impossibility conditions for anonymity even against this wider class of protocols, but with the following assumptions.
the protocols do not use a secret sharing scheme that generates w < k*n shares for n messages where at least k shares are necessary to reconstruct each the n messages correctly, without using any trusted third party, with a communication of O(n) and constant latency overhead.
We also assume that one of the users who send the shares is the actual sender. We do not consider the scenario where a set of users send shares for Alice, however Alice is not part of that set. In that case, Alice will have to explicitly distribute the shares to the other users directly or through a trusted third party. In that case, anonymity is bounded by the impossibility conditions for mix-net-type protocols.
A compromised node can always relate incoming and outgoing packets. More precisely, if two packets enter a node and two packets leave a node, the node is able to tell how much information of each incoming packet is encoded in which outgoing packet.
Read our complete tech report here.
Although our work shows that hybrid protocols have better chance against compromising adversaries, they are still bound by the impossibility constraints. The only possible way to break that impossibility constraints is to break an assumption on the protocols. One such plausible direction is to break our assumption on user-coordination.
Challenge: If a protocol can use a secret sharing scheme that generates w < k*n shares for n messages such that k shares are sufficient to reconstruct all the n messages correctly, without using any trusted third party, with a communication of O(n) and constant latency overhead, that protocol can break anonymity trilemma.