JOINT COMPUTER SCIENCE / ELECTRICAL & COMPUTER ENGINEERING COLLOQUIUM & SECURITY SEMINAR

Anonymity in Peer-to-peer Systems

Nikita Borisov
Department of Computer Science
University of California, Berkeley

April 20 (Wednesday), 2005 at 10:00 a.m.
2405 Siebel Center for Computer Science

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.

Bio:
Nikita Borisov received his BMath degree from the University of Waterloo in Computer Science and Pure Math. Since then, he has been pursuing a Ph.D. at UC Berkeley, focusing on problems in security and privacy of Internet-scale systems. His research covers a wide range of topics, but his recent work has been on privacy enhancing technologies and anonymity. He expects to receive his degree in May of 2005.
 

Reception after the talk in the 2nd Floor Atrium of Siebel Center.