Paper 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.
Note: The PPR anonymity model proposed in this paper is completely different from k-anonymity model in use.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Foundations
- Publication info
- Published elsewhere. UCLA Computer Science Technical Report CSD-TR050016
- Keywords
- anonymity
- Contact author(s)
- jkong @ cs ucla edu
- History
- 2005-05-05: received
- Short URL
- https://ia.cr/2005/132
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/132,
author = {Jiejun Kong},
title = {Formal Notions of Anonymity for Peer-to-peer Networks},
howpublished = {Cryptology ePrint Archive, Paper 2005/132},
year = {2005},
note = {\url{https://eprint.iacr.org/2005/132}},
url = {https://eprint.iacr.org/2005/132}
}
