Probabilistic analysis of onion routing in a black-box model
Abstract
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication in the Universally Composable (UC) framework that abstracts the essential properties of onion routing in the presence of an active adversary who 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, in the limit as the network gets large, 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 shown to be comparable to the best-case anonymity against an adversary that controls a fraction √ b .
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2012
- Source ID
- 10.1145/2382448.2382452
Entities
People
- Aaron M. Johnson
- Joan Feigenbaum
- Paul Syverson
Organizations
- Army Research Office
- National Science Foundation
- United States Naval Research Laboratory
- Yale University