Cryptology ePrint Archive: Report 2005/132

Formal Notions of Anonymity for Peer-to-peer Networks

Jiejun Kong

Abstract: Providing anonymity support for peer-to-peer (P2P) overlay networks is critical. Otherwise, potential privacy attacks (e.g., network address traceback) may deter a storage source from providing the needed data. In this paper we use this practical application scenario to verify our observation that network-based anonymity can be modeled as a complexity based cryptographic problem. We show that, if the routing process between senders and recipients can be modeled as abstract entities, network-based anonymity becomes an analogy of cryptography. In particular, perfect anonymity facing an unbounded traffic analyst corresponds to Shannon's perfect secrecy facing an unbounded cryptanalyst. More importantly, in this paper we propose Probabilistic Polynomial Route (PPR) model, which is a new polynomially-bounded anonymity model corresponding to the Probabilistic Polynomial Time (PPT) model in cryptography. Afterwards, network-based anonymity attacks are with no exception in BPP. This phenomenon has not been discovered in previous anonymity research.

Category / Keywords: foundations / anonymity

Publication Info: UCLA Computer Science Technical Report CSD-TR050016

Date: received 3 May 2005

Contact author: jkong at cs ucla edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: The PPR anonymity model proposed in this paper is completely different from k-anonymity model in use.

Version: 20050505:035542 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]