Aaron Johnson

Research

A general theme of my research is designing protocols to provide good, provable tradeoffs between privacy and utility. Specifically, I am working on private data publishing and anonymous communication protocols.

In private data publishing I am interested in exploring and applying formal notions of privacy. In particular, I am interested in applying differential privacy to concrete problems in data publishing.

The goal of my work on anonymous communication protocols is to formally specify them 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. Trust-based Anonymous Communication: Adversary Models and Routing Algorithms [pdf]
   with Paul Syverson, Roger Dingledine, and Nick Mathewson
   In Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS 2011)
   Show abstract

   We introduce a novel model of routing security that incorporates the ordinarily overlooked variations in trust that users have for different parts of the network. We focus on anonymous communication, and in particular onion routing, although we expect the approach to apply more broadly.
   This paper provides two main contributions. First, we present a novel model to consider the various security concerns for route selection in anonymity networks when users vary their trust over parts of the network. Second, to show the usefulness of our model, we present as an example a new algorithm to select paths in onion routing. We analyze its effectiveness against deanonymization and other information leaks, and particularly how it fares in our model versus existing algorithms, which do not consider trust. In contrast to those, we find that our trust-based routing strategy can protect anonymity against an adversary capable of attacking a significant fraction of the network.

2. Preventing Active Timing Attacks in Low-Latency Anonymous Communication (Extended Abstract) [pdf]
   
   • Technical Report (Full Version) [pdf]
   with Joan Feigenbaum and Paul Syverson
   In Proceedings of the 10th Privacy Enhancing Technologies Symposium (PETS 2010), pp. 166-183.
   Show abstract

   Low-latency anonymous communication protocols in general, and the popular onion-routing protocol in particular, are broken against simple timing attacks. While there have been few proposed solutions to this problem when the adversary is active, several padding schemes have been proposed to defend against a passive adversary that just observes timing patterns. Unfortunately active adversaries can break padding schemes by inserting delays and dropping messages.
   We present a protocol that provides anonymity against an active adversary by using a black-box padding scheme that is effective against a passive adversary. Our protocol reduces, in some sense, providing anonymous communication against active attacks to providing a padding scheme against passive attacks.
   Our analytical results show that anonymity can be made arbitrarily good at the cost of some added latency and required bandwidth. We also perform measurements on the Tor network to estimate the real-world performance of our protocol, showing that the added delay is not excessive.

3. More Anonymous Onion Routing Through Trust [pdf]
   with Paul Syverson
   In Proceedings of the 22nd IEEE Computer Security Foundations Symposium (CSF 2009), pp. 3-12.
   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.

4. 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.

5. 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.

6. 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.

7. 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.

• Ph.D. Thesis: 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.

• Undergraduate Thesis: Routing Network Flow Among Selfish Agents [pdf] [ps]
  Show abstract

  We consider the problems posed by routing flow in a network populated by self-interested agents. Standard node-cost and edge-cost network models are compared and a mapping between them is described. The existence of Nash equilibria when flow cannot be split is established in several cases. Braess's paradox is shown to exist when the number of users is finite and flow is unsplittable. Finally, optimizing the flow routing with polynomial and capacity cost functions is shown to be hard to compute and to approximate.