Anonymity in Peer-to-peer Systems

As more of our activities are carried out online, technologies for protecting our privacy are becoming increasingly important. I will discuss one such technology – anonymity – in the context of peer-to-peer systems. To begin, I will talk about new techniques to study anonymity in this context. Anonymity in existing p2p systems has only been analyzed with respect to known attacks, while more general information-theoretic metrics have only been applied to small-scale systems. I show how to use simulations and probabilistic models to compute (or approximate) the metrics for large p2p systems and derive information-theoretic bounds on anonymity. I have applied these techniques to Freenet, an anonymous p2p publishing system, and identified significant weaknesses in its design.

My analysis shows that even when Freenet provides good anonymity on average, there is a lot of variability and some of the users should expect to receive little or no anonymity protection. I argue that to provide a more uniform level of anonymity, a structured p2p design is necessary. I present such a design based on de Bruijn networks and random walks. De Bruijn networks have several important properties that make them better suited for anonymity than other structures, such as Chord or Pastry. My design provides a consistent level of anonymity to all users while maintaining logarithmic routing performance, as shown by simulations and information-theoretic analysis, and can be used for a variety of applications where anonymity is desired.