Skip to content

Robustness Guarantees for Anonymity

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationIEEE Computer Security Foundations Symposium - CSF 2010
Publisher or commissioning bodyIEEE Computer Society
DatePublished - 2010


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.

Additional information

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

View research connections

Related faculties, schools or groups