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.