Robustness Guarantees for Anonymity

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.