Rome: Performance and Anonymity using Route Meshes

Krishna P. N. Puttaswamy
Alessandra Sala
Ben Y. Zhao

The 28th IEEE International Conference on Computer Communications (INFOCOM Mini-symposium 2009)

[Full Text in PDF Format, 124KB]
[Full Text in Compressed Postscript Format, 144KB]

Paper Abstract

Deployed anonymous networks such as Tor focus on delivering messages through end-to-end paths with high anonymity. Selection of routers in the anonymous path construction is either performed randomly, or relies on self-described resource availability at routers, making systems vulnerable to low-resource attacks. In this paper, we investigate an alternative router and path selection mechanism for constructing efficient end-to-end paths with low loss of path anonymity. We propose a novel construct called a "route mesh," and a dynamic programming algorithm that determines optimal-latency paths from many random samples using only a small number of end-to-end measurements. We prove analytically that our path search algorithm finds the optimal path, and requires exponentially lower number of measurements compared to a standard measurement approach. In addition, our analysis shows that route meshes incur only a small loss in anonymity for its users.