Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks

A major challenge in network communication is providing anonymity and privacy without significant increase in latency and message complexity. While it is known how to secure the contents of messages via proper encryption techniques, it is less clear how to ensure that who is communicating with whom remains private, too. Currently used anonymity technologies such as the Tor network (used by millions daily) are practical but do not provide provable anonymity guarantees; in fact, security researchers have demonstrated that Tor is vulnerable to a type of Internet attack called traffic analysis. How to guarantee anonymity without rendering current systems too impractical remains an open question of high relevance to many widely used applications. This project create and disseminates algorithms that implement rigorous and efficient solutions to anonymous communication. The project also includes educational initiatives at the graduate and undergraduate levels to build a bigger workforce in the crucial area of privacy, security and computer science more generally. This project addresses the fundamental challenge of guaranteeing anonymity in network communications. Techniques for obscuring meta-information about who is communicating with whom, when, and for how long inevitably involve increased communication (e.g., by rerouting communication through intermediate nodes and/or adding decoy messages). This in turn may lead to network congestion and communication delays. Thus, a crucial question of both theoretical and practical importance is to understand the trade-offs between security and message complexity in network communications under various privacy measures and adversarial models. A second challenge is to design provably secure and efficient anonymous communication schemes in realistic communications scenarios, such as node churn and iterative two-way communications. The team of researchers will address these challenges along two facets: (1) Designing routing schemes so that traffic patterns, possibly altered by malicious nodes, do not reveal any metadata; and (2) Designing cryptographically secure tools (such as cryptographic onions) to secure data even when the network participants responsible for relaying it are potentially adversarial. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.