Robustness Guarantees for Anonymity

Gilles Barthe, Alejandro Hevia, Zhengqin Luo, Tamara Rezk, Bogdan Warinschi

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)


Anonymous communication protocols must achieve two seemingly contradictory goals: {\em privacy} (informally, they must guarantee the anonymity of the parties that send/receive information), and {\em robustness} (informally, they must ensure that the messages are not tampered). However, the long line of research that defines and analyzes the security of such mechanisms focuses almost exclusively on the former property and ignores the latter. In this paper, we initiate a rigorous study of robustness properties for anonymity protocols. We identify and formally define, using the style of modern cryptography, two related but distinct flavors of robustness. Our definitions are general ({\it e.g.} they strictly generalize the few existent notions for particular protocols) and flexible ({\it e.g.} they can be easily adapted to purely combinatorial/probabilistic mechanisms). We demonstrate the use of our definitions through the analysis of several anonymity mechanisms (Crowds, broadcast-based mix-nets, DC-nets, Tor). Notably, we analyze the robustness of a protocol by Golle and Juels for the dining cryptographers problem, identify a robustness-related weakness of the protocol, and propose and analyze a stronger version.
Translated title of the contributionRobustness Guarantees for Anonymity
Original languageEnglish
Title of host publicationIEEE Computer Security Foundations Symposium - CSF 2010
PublisherIEEE Computer Society
Publication statusPublished - 2010

Bibliographical note

Other page information: 91-106
Conference Proceedings/Title of Journal: 23rd IEEE Computer Security Foundations Symposium - CSF 2010
Other identifier: 2001235


Dive into the research topics of 'Robustness Guarantees for Anonymity'. Together they form a unique fingerprint.

Cite this