Paper 2019/1433

T0RTT: Non-Interactive Immediate Forward-Secret Single-Pass Circuit Construction

Sebastian Lauer, Kai Gellert, Robert Merget, Tobias Handirk, and Jörg Schwenk


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 20th Privacy Enhancing Technologies Symposium (PETS 2020)
Toronion routingcircuit constructionnTor handshake0-RTTpuncturable encryptionforward secrecy
Contact author(s)
sebastian lauer @ rub de
kai gellert @ uni-wuppertal de
2019-12-10: received
Short URL
Creative Commons Attribution


      author = {Sebastian Lauer and Kai Gellert and Robert Merget and Tobias Handirk and Jörg Schwenk},
      title = {T0RTT: Non-Interactive Immediate Forward-Secret Single-Pass Circuit Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1433},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.