Relay selection for optimal delay anonymity tradeoff in anonymous networks

An analytical framework is presented to integrate link padding mechanisms to the functioning of intermediate relays in anonymous networks such that a desired degree of anonymity- secrecy of source destination pairs- is achieved against timing analysis without adding significant latency. In particular, the relays for routing and the degree of link padding at each relay are chosen to optimize the tradeoff between anonymity from timing analysis, as measured by Shannon entropy of source destination pairs, and the average latency. Optimization of the tradeoff is shown to require exponential complexity, and a suboptimal algorithm is presented that is shown numerically to perform close to the optimal, but only requires linear complexity. In addition, an incremental optimization is presented for a new user to be added optimally to an existing system without altering the prevalent routes.