Association for Computing Machinery
The authors study provably secure anonymity. They begin with rigorous definition of anonymity against wide range of computationally bounded attackers, including eavesdroppers, malicious peers, malicious destinations, and their combinations. Their definition is generic, and captures different notions of anonymity (e.g., un-observability and sender anonymity). They then study the feasibility of ultimate anonymity: the strongest-possible anonymity requirements and adversaries. They show there is a protocol satisfying this requirement, but with absurd (although polynomial) inefficiency and overhead.