Aaron Johnson

Research

The focus of my dissertation research has been anonymous communication protocols. The goal of my work is to formally specify anonymity protocols and rigorously analyze their properties. In particular, I am interested in provably good tradeoffs between anonymity, latency, and message complexity.

My other interests involve other areas of computer science theory, including computational finance, algorithmic game theory, privacy protocols, and probabilistic analysis of algorithms and protocols.

Publications

1. More Anonymous Onion Routing Through Trust [pdf]
   with Paul Syverson
   To appear in the 22nd IEEE Computer Security Foundations Symposium (CSF 2009)
   Show abstract

   We consider using trust information to improve the security of onion-routing networks. In particular, we introduce a model of trust in network nodes and use it to design path-selection strategies that minimize the probability that the adversary can successfully perform a correlation attack. We first describe the general case in which onion routers can be assigned arbitrary levels of trust. Selecting a strategy can be formulated in a straightforward way as a linear program, but it is exponential in size. We thus analyze a natural simplification of path selection for this case. More importantly, however, when choosing routes in practice, only a very coarse assessment of trust in specific onion routers is likely to be feasible. Therefore, we focus next on the special case in which there are only two trust levels. For this more practical case we identify three optimal route-selection strategies such that at least one is optimal, depending on the trust levels of the two classes, their size, and the reach of the adversary. This can yield practical input into routing decisions . We set out the relevant parameters and choices for making such decisions.

2. Online and Offline Selling in Limit Order Markets [pdf]
   with Kevin L. Chang
   In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE 2008), pp. 41-52.
   Show abstract

   Completely automated electronic securities exchanges and algorithms for trading in these exchanges have become very important for modern finance. Kakade et al. introduced the limit order market model, which is a prevalent paradigm in electronic markets. In this paper, we consider both online and offline algorithms for maximizing revenue when selling in limit order markets. We first prove that the standard reservation price algorithm has an optimal competitive ratio for this problem. This ratio is not constant, and so we consider computing solutions offline. We show that the offline optimization problem is NP-hard, even for very restricted instances. We complement the hardness result by presenting an approximation scheme that runs in polynomial time for a wide class of instances.

3. Probabilistic Analysis of Onion Routing in a Black-box Model (Extended abstract) [pdf]
   with Joan Feigenbaum and Paul Syverson
   In Proceedings of the 2007 ACM Workshop on Privacy in Electronic Society (WPES 2007), pp. 1-10.
   Show abstract

   We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication that abstracts the essential properties of onion routing in the presence of an active adversary that controls a portion of the network and knows all a priori distributions on user choices of destination. Our results quantify how much the adversary can gain in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that a user u's anonymity is worst either when the other users always choose the destination u is least likely to visit or when the other users always choose the destination u chooses. This worst-case anonymity with an adversary that controls a fraction b of the routers is comparable to the best-case anonymity against an adversary p that controls a fraction √b.

4. Private Web Search [pdf] [software]
   with Felipe Saint-Jean, Dan Boneh, and Joan Feigenbaum
   In Proceedings of the 2007 ACM Workshop on Privacy in Electronic Society (WPES 2007), pp. 84-90.
   Show abstract

   Web search is currently a source of growing concern about personal privacy. It is an essential and central part of most users' activity online and therefore one through which a significant amount of personal information may be revealed. To help users protect their privacy, we have designed and implemented Private Web Search (PWS), a usable client-side tool that minimizes the information that users reveal to a search engine. Our tool protects users against attacks that involve active components and timing information, to which more general Web-browsing privacy tools (including the combination of FoxTor and Privoxy) are vulnerable. PWS is a Firefox plugin that functions as an HTTP proxy and as a client for the Tor anonymity network. It configures Firefox so that search queries executed from the PWS search box are routed through the HTTP proxy and Tor client, filtering potentially sensitive or identifying components of the request and response.

5. A Model of Onion Routing with Provable Anonymity [pdf]
   with Joan Feigenbaum and Paul Syverson
   In Proceedings of Financial Cryptography and Data Security '07 (FC 2007), pp. 57-71.
   Show abstract

   Onion routing is a scheme for anonymous communication that is designed for practical use. Until now, however, it has had no formal model and therefore no rigorous analysis of its anonymity guarantees. We give an IO-automata model of an onion-routing protocol and, under possibilistic definitions, characterize the situations in which anonymity and unlinkability are guaranteed.

• Dissertation: Design and Analysis of Efficient Anonymous-Communication Protocols [pdf]
  Show abstract

  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.