International Association
for Cryptologic Research

Maintaining privacy on the Internet with the presence of powerful adversaries such as nation-state attackers is a challenging topic, and the Tor project is currently the most important tool to protect against this threat. The circuit construction protocol (CCP) negotiates cryptographic keys for Tor circuits, which overlay TCP/IP by routing Tor cells over n onion routers. The current circuit construction protocol provides strong security guarantees such as forward secrecy by exchanging O(n^2) messages.

For several years it has been an open question if the same strong security guarantees could be achieved with less message overhead, which is desirable because of the inherent latency in overlay networks. Several publications described CCPs which require only O(n) message exchanges, but significantly reduce the security of the resulting Tor circuit. It was even conjectured that it is impossible to achieve both message complexity O(n) and forward secrecy immediately after circuit construction (so-called immediate forward secrecy).

Inspired by the latest advancements in zero round-trip time key exchange (0-RTT), we present a new CCP protocol Tor 0-RTT (T0RTT). Using modern cryptographic primitives such as puncturable encryption allow to achieve immediate forward secrecy using only O(n) messages. We implemented these new primitives to give a first indication of possible problems and how to overcome them in order to build practical CCPs with O(n) messages and immediate forward secrecy in the future.