Pisces: Anonymous Communication Using Social Networks

Prateek Mittal, Matthew Wright, Nikita Borisov

Research output: Contribution to conferencePaperpeer-review

28 Scopus citations


The architectures of deployed anonymity systems such as Tor suffer from two key problems that limit user's trust in these systems. First, paths for anonymous communication are built without considering trust relationships between users and relays in the system. Second, the network architecture relies on a set of centralized servers. In this paper, we propose Pisces, a decentralized protocol for anonymous communications that leverages users' social links to build circuits for onion routing. We argue that such an approach greatly improves the system's resilience to attackers. A fundamental challenge in this setting is the design of a secure process to discover peers for use in a user's circuit. All existing solutions for secure peer discovery leverage structured topologies and cannot be applied to unstructured social network topologies. In Pisces, we discover peers by using random walks in the social network graph with a bias away from highly connected nodes to prevent a few nodes from dominating the circuit creation process. To secure the random walks, we leverage the reciprocal neighbor policy: if malicious nodes try to exclude honest nodes during peer discovery so as to improve the chance of being selected, then honest nodes can use a tit-for-tat approach and reciprocally exclude the malicious nodes from their routing tables. We describe a fully decentralized protocol for enforcing this policy, and use it to build the Pisces anonymity system.

Original languageEnglish (US)
StatePublished - 2013
Externally publishedYes
Event20th Annual Network and Distributed System Security Symposium, NDSS 2013 - San Diego, United States
Duration: Feb 24 2013Feb 27 2013


Conference20th Annual Network and Distributed System Security Symposium, NDSS 2013
Country/TerritoryUnited States
CitySan Diego

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Pisces: Anonymous Communication Using Social Networks'. Together they form a unique fingerprint.

Cite this