Design and Analysis of Efficient Anonymous-Communication Protocols

Full textClick to download.
CitationPhD Thesis, Yale University Computer Science Department, 2009
AuthorAaron Johnson


Research into protocols for anonymous communication in networks has yielded many designs and a wide range of functionality and performance options. Of these, only a few have been successful in practice. The experience in fielded systems emphasizes the following criteria for designing anonymous-communication protocols: communication functionality, anonymity, latency, and message complexity. Therefore, in this thesis we explore understanding and improving the performance of anonymous-communication protocols according to these criteria. To provide high confidence in our analysis against a malicious adversary, we formally model such protocols and rigorously analyze them according to precise definitions. The first subject of our analysis is the onion-routing protocol. Onion routing is a successful protocol for anonymous communication in widespread public use. However, its anonymity has not received much rigorous analysis. Therefore, in the first half of the thesis, we model the protocol and its environment, and we analyze the resulting anonymity properties. Our results show that onion routing provides unsatisfactory anonymity against a realistic adversary that controls some fraction of the network. In particular, the protocol faces an upper limit on anonymity that depends only on the size of the adversary. Therefore, in the last half of the thesis, we consider two ways to get past this limit: trust information and a new protocol design. We first suppose that users have external trust information about the network that helps them avoid parts that are controlled by the adversary. Then we consider using this information to improve the anonymity provided by onion routing. Under a model of trust, we come up with practical and provable improvements. Next we consider a new protocol that avoids a major weakness in onion routing: timing attacks. The protocol uses explicit timing and redundancy as its key techniques, and we prove that it can provide arbitrarily high anonymity. Finally, this protocol requires adding delays to smooth out variable latency in the underlying network. We estimate the magnitudes of these delays by performing measurements on a live anonymity network. Our results suggest that the added delays likely result in a small constant-factor increase over onion routing.

Back to publications
Back to previous page