Fully non-interactive onion routing with forward secrecy

Onion routing is a privacy-enabling protocol that allows users to establish anonymous channels over a public network. In such a protocol, parties send their messages through n anonymizing servers (called a circuit) using several layers of encryption. Several proposals for onion routing have been published in recent years, and TOR, a real-life implementation, provides an onion routing service to thousands of users over the Internet. This paper puts forward a new onion routing protocol which outperforms TOR by achieving forward secrecy in a fully non-interactive fashion, without requiring any communication from the router and/or the users and the service provider to update time-related keys. We compare this to TOR which requires O(n^2) rounds of interaction to establish a circuit of size n . In terms of the computational effort required to the parties, our protocol is comparable to TOR, but the network latency associated with TOR’s high round complexity ends up dominating the running time. Compared to other recently proposed alternative to TOR, such as the PB-OR (PETS 2007) and CL-OR (CCS 2009) protocols, our scheme still has the advantage of being non-interactive (both PB-OR and CL-OR require some interaction to update time-sensitive information), and achieves similar computational performances. We performed implementation and simulation tests that confirm our theoretical analysis. Additionally, while comparing our scheme to PB-OR, we discovered a flaw in the security of that scheme which we repair in this paper. Our solution is based on the application of forward secure encryption. We design a forward secure encryption scheme (of independent interest) to be used as the main encryption scheme in our onion routing protocol.