Paper 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 different 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.
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Minor revision. WPES 2013
- Keywords
- anonymity
- Contact author(s)
- nethanel gelernter @ gmail com
- History
- 2013-09-12: last of 2 revisions
- 2013-08-30: received
- See all versions
- Short URL
- https://ia.cr/2013/531
- License
-
CC BY