A certificateless approach to onion routing

Onion routing protocols allow users to establish anonymous channels to preserve their privacy over a public network. Several protocols implementing this primitive have been proposed in recent years, and The onion routing network (Tor), a real-life implementation, provides an onion routing service to thousands of users over the Internet. This paper presents Certificateless Onion Routing a new approach to the problem. Starting from the identity-based solution (PB-OR) of Kate et al. (ACM TISSEC 2000), we adopt the certificateless setting introduced by Al-Riyami and Paterson in 2003. Such a setting is particularly well suited in practice as it retains the good aspects of identity-based cryptography (no PKI is required) and traditional public key cryptography (there is no key escrow). Next, we present a novel certificateless key-encapsulation mechanism and we show how to turn it into a very efficient (and provably secure!) certificateless onion routing protocol. When compared with Tor and PB-OR, our protocol offers better performances, especially when current security levels (i.e., 128 bits) are considered. In particular, our scheme significantly improves the computational costs required from each router. In this sense, our solution is up to 7 times faster than PB-OR and up to 11 times faster than Tor.