Paper 2017/954

Anonymity Trilemma: Strong Anonymity, Low Bandwidth Overhead, Low Latency---Choose Two

Debajyoti Das, Sebastian Meiser, Esfandiar Mohammadi, and Aniket Kate


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 a 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 as a necessary constraint a relationship 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
das48 @ purdue edu
2018-03-02: last of 2 revisions
2017-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Debajyoti Das and Sebastian Meiser and Esfandiar Mohammadi and Aniket Kate},
      title = {Anonymity Trilemma: Strong Anonymity, Low Bandwidth Overhead, Low Latency---Choose Two},
      howpublished = {Cryptology ePrint Archive, Paper 2017/954},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.