Abstract
Rome: Performance and Anonymity using Route Meshes
by: Krishna P. N. Puttaswamy, Alessandra Sala, Omer Egecioglu, and Ben Y. Zhao
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 from each router, which makes the system 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. Meanwhile, experimental deployment of our anonymous routers on Planet-lab shows dramatic improvements in path selection quality using very small route meshes that incur low measurement overheads.
Keywords:
None.
Date:
Sep 2008
Document: 2008-11
