CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
Purdue University - Discovery Park
Center for Education and Research in Information Assurance and Security

Anonymity Trilemma : Strong Anonymity, Low Bandwidth Overhead, Low Latency – Choose Two.

Debajyoti Das - Purdue University

Apr 11, 2018


Over the last three decades, several anonymous communication (AC) protocols have been proposed towards improving users' privacy over the internet. Among those, the Tor protocol has been particularly successful. Thanks to its low communication latency and low bandwidth overhead, Tor today is employed by millions of users worldwide. Nevertheless, its anonymity is known to be broken in the presence of global adversaries. AC protocols like the dining cryptographers network provide anonymity even in the presence of global adversaries at the expense of bandwidth overhead, while others such as the mixing network designs improve anonymity at the expense of higher latency.
In this work, we investigate 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.
We further study anonymity against a stronger global passive adversary that can additionally passively compromise some of the AC protocol nodes. For a given number of compromised nodes, we derive necessary constraints between bandwidth and latency overhead whose violation make it impossible for an AC protocol to achieve strong anonymity. We analyze prominent AC protocols from the literature and depict to which extent those satisfy our necessary constraints. Our fundamental necessary constraints offer a guideline not only for improving existing AC systems but also for designing novel AC protocols with non-traditional bandwidth and latency overhead choices.

Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52, West Lafayette Campus. More information...


The views, opinions and assumptions expressed in these videos are those of the presenter and do not necessarily reflect the official policy or position of CERIAS or Purdue University. All content included in these videos, are the property of Purdue University, the presenter and/or the presenter’s organization, and protected by U.S. and international copyright laws. The collection, arrangement and assembly of all content in these videos and on the hosting website exclusive property of Purdue University. You may not copy, reproduce, distribute, publish, display, perform, modify, create derivative works, transmit, or in any other way exploit any part of copyrighted material without permission from CERIAS, Purdue University.