Cryptology ePrint Archive: Report 2014/087

AnoA: A Framework For Analyzing Anonymous Communication Protocols

Michael Backes and Aniket Kate and Praveen Manoharan and Sebastian Meiser and Esfandiar Mohammadi

Abstract: Protecting individuals’ privacy in online communications has become a challenge of paramount importance. To this end, anonymous communication (AC) protocols such as the widely used Tor network have been designed to provide anonymity to their participating users. While AC protocols have been the subject of several security and anonymity analyses in the last years, there still does not exist a framework for analyzing complex systems such as Tor and their different anonymity properties in a unified manner.

In this work we present AnoA: a generic framework for defining, analyzing, and quantifying anonymity properties for AC protocols. AnoA relies on a novel relaxation of the notion of (computational) differential privacy, and thereby enables a unified quantitative analysis of well- established anonymity properties, such as sender anonymity, sender unlinkability, and relationship anonymity. While an anonymity analysis in AnoA can be conducted in a purely information theoretical manner, we show that the protocol’s anonymity properties established in AnoA carry over to secure cryptographic instantiations of the protocol. We exemplify the applicability of AnoA for analyzing real-life systems by conducting a thorough analysis of the anonymity properties provided by the Tor network against passive adversarys. Our analysis significantly improves on known anonymity results from the literature.

Category / Keywords: foundations / anonymity analysis, differential privacy, unlinkability, relationship anonymity, Tor

Original Publication (with major differences): 26th IEEE Computer Security Foundations Symposium (CSF) 2013

Date: received 5 Feb 2014

Contact author: meiser at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Note: Compared to the CSF'13 version, this version enhances the AnoA framework by making the anonymity definitions as well as the corresponding privacy games adaptive. It also introduces the concept of adversary classes for restricting the capabilities of adversaries to model realistic attack scenarios.

Version: 20140207:152210 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]