Comprehensive Anonymity Trilemma: User Coordination is not enough
Authors: Debajyoti Das (Purdue University), Sebastian Meiser (Visa Research), Esfandiar Mohammadi (Universitaet zu Luebeck), Aniket Kate (Purdue University)
Volume: 2020
Issue: 3
Pages: 356–383
DOI: https://doi.org/10.2478/popets-2020-0056
Abstract: For anonymous communication networks (ACNs), Das et al. recently confirmed a long-suspected trilemma result that ACNs cannot achieve strong anonymity, low latency overhead and low bandwidth overhead at the same time. Our paper emanates from the careful observation that their analysis does not include a relevant class of ACNs with what we call user coordination where users proactively work together towards improving their anonymity. We show that such protocols can achieve better anonymity than predicted by the above trilemma result. As the main contribution, we present a stronger impossibility result that includes all ACNs we are aware of. Along with our formal analysis, we provide intuitive interpretations and lessons learned. Finally, we demonstrate qualitatively stricter requirements for the Anytrust assumption (all but one protocol party is compromised) prevalent across ACNs.
Keywords: anonymity, trilemma
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
