## An Indistinguishability-based Characterization of Anonymous Channels

**Author:**
A.H. and Daniele Micciancio

**Abstract:**

We revisit the problem of anonymous communication,
in which users wish to send messages to each other without revealing
their identities.
We propose a novel framework to organize and compare anonymity
definitions.
In this framework,
we present simple and practical definitions for anonymous channels
in the context of computational indistinguishability.
The notions seem to capture the intuitive properties of several
types of anonymous channels (Pfitzmann and Kohntopp 1991)
(eg. sender anonymity and unlinkability).
We justify these notions by showing they naturally capture
practical scenarios where information is unavoidably leaked
in the system.
Then, we compare the notions and we show they form a natural hierarchy
for which we exhibit non-trivial implications.
In particular, we show how to implement stronger notions from weaker ones
using cryptography and dummy traffic -- in a provably optimal way.
With these tools, we revisit the security of previous anonymous channels
protocols, in particular constructions based on broadcast networks
(Blaze et al. 2003), anonymous broadcast (Chaum 1981),
and mix networks (Groth 2003, Nguyen et al. 2004).
Our results give generic, optimal
constructions to transform known protocols into
new ones that achieve the strongest notions of anonymity.

**Ref:** In Proceedings of Privacy Enhancing Technologies Symposium
(PETS 2008), Leuvren, Belgium, July 23-25, 2008,
Lecture Notes in Computer Science 5134, pp. 24-43,
Springer-Verlag, 2008.

**Revised paper:**
Available as
Compressed Postscript,
Postscript, and
PDF.

**Talk Slides:** Available as
pdf (Jul.28, 2008)