TY - GEN
T1 - PIR-Tor
T2 - 20th USENIX Security Symposium
AU - Mittal, Prateek
AU - Olumofin, Femi
AU - Troncoso, Carmela
AU - Borisov, Nikita
AU - Goldberg, Ian
N1 - Publisher Copyright:
© 2011 by The USENIX Association.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84962047384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84962047384&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84962047384
T3 - Proceedings of the 20th USENIX Security Symposium
SP - 475
EP - 490
BT - Proceedings of the 20th USENIX Security Symposium
PB - USENIX Association
Y2 - 8 August 2011 through 12 August 2011
ER -