PIR-Tor: Scalable anonymous communication using private information retrieval

Prateek Mittal, Femi Olumofin, Carmela Troncoso, Nikita Borisov, Ian Goldberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

59 Scopus citations


Existing anonymous communication systems like Tor do not scale well as they require all users to maintain up-todate information about all available Tor relays in the system. Current proposals for scaling anonymous communication advocate a peer-to-peer (P2P) approach. While the P2P paradigm scales to millions of nodes, it provides new opportunities to compromise anonymity. In this paper, we step away from the P2P paradigm and advocate a client-server approach to scalable anonymity. We propose PIR-Tor, an architecture for the Tor network in which users obtain information about only a few onion routers using private information retrieval techniques. Obtaining information about only a few onion routers is the key to the scalability of our approach, while the use of private retrieval information techniques helps preserve client anonymity. The security of our architecture depends on the security of PIR schemes which are well understood and relatively easy to analyze, as opposed to peer-to-peer designs that require analyzing extremely complex and dynamic systems. In particular, we demonstrate that reasonable parameters of our architecture provide equivalent security to that of the Tor network. Moreover, our experimental results show that the overhead of PIR-Tor is manageable even when the Tor network scales by two orders of magnitude.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th USENIX Security Symposium
PublisherUSENIX Association
Number of pages16
ISBN (Electronic)9781931971874
StatePublished - 2011
Externally publishedYes
Event20th USENIX Security Symposium - San Francisco, United States
Duration: Aug 8 2011Aug 12 2011

Publication series

NameProceedings of the 20th USENIX Security Symposium


Conference20th USENIX Security Symposium
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'PIR-Tor: Scalable anonymous communication using private information retrieval'. Together they form a unique fingerprint.

Cite this