Cryptology ePrint Archive: Report 2013/531

On the Limits of Provable Anonymity

Nethanel Gelernter and Amir Herzberg

Abstract: We study provably secure anonymity, focusing on ultimate anonymity - strongest-possible anonymity requirements and adversaries. We begin with rigorous definition of anonymity against wide range of computationally-bounded attackers, including eavesdroppers, malicious peers, malicious destina-tions, and their combinations. Following the work of Hevia and Micciancio [15], our definition is generic, and captures dierent notions of anonymity (e.g., unobservability and sender anonymity). We then study the feasibility of ultimate anonymity. We show there is a protocol satisfying this requirement, but with absurd (although polynomial) inefficiency and overhead. We show that such inefficiency and overhead is unavoidable for `ultimate anonymity'. We then present a slightly-relaxed requirement and present feasible protocols for it.

Category / Keywords: anonymity

Original Publication (with minor differences): WPES 2013

Date: received 25 Aug 2013, last revised 12 Sep 2013

Contact author: nethanel gelernter at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20130912:094033 (All versions of this report)

Short URL: ia.cr/2013/531

Discussion forum: Show discussion | Start new discussion