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)
-
PDF
- 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
BibTeX
@misc{cryptoeprint:2013/531,
author = {Nethanel Gelernter and Amir Herzberg},
title = {On the Limits of Provable Anonymity},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/531},
year = {2013},
url = {https://eprint.iacr.org/2013/531}
}
