Scalable anonymous communication with provable security

A key problem in Tor's architecture is that it requires users to maintain a global view of the system, which will become costly as the size of the network increases. Several peer-to-peer approaches have been proposed in order to alleviate the scalability concerns of the Tor network, but they are only able to provide heuristic security; in fact, the security community has been quite successful at breaking the state of the art systems using both passive and active attacks. In this paper, we explore new primitives for scalable anonymous communication, with a focus on providing provable security guarantees. First, we propose a new approach for secure peer-to-peer anonymous communication based on a reciprocal neighbor policy. Secondly, we propose PIR-Tor, a client-server scalable architecture for anonymous communications based on Private Information Retrieval.