Practical and Provably Secure Onion Routing
This work addresses the need for secure and efficient anonymous communication channels, which is crucial for privacy in applications like Tor, but it appears incremental as it builds on existing onion routing concepts with provable security enhancements.
The paper tackled the problem of designing onion routing protocols that are both practical and provably secure against standard adversary models, achieving a differentially private solution for active adversaries with specific round and transmission complexities.
In an onion routing protocol, messages travel through several intermediaries before arriving at their destinations, they are wrapped in layers of encryption (hence they are called "onions"). The goal is to make it hard to establish who sent the message. It is a practical and widespread tool for creating anonymous channels. For the standard adversary models -- network, passive, and active -- we present practical and provably secure onion routing protocols. Akin to Tor, in our protocols each party independently chooses the routing paths for his onions. For security parameter $λ$, our differentially private solution for the active adversary takes $O(\log^2λ)$ rounds and requires every participant to transmit $O(\log^{4} λ)$ onions in every round.