Paper 2015/008

Post-Quantum Forward-Secure Onion Routing (Future Anonymity in Today’s Budget)

Satrajit Ghosh and Aniket Kate


The onion routing (OR) network Tor provides anonymity to its users by routing their encrypted traffic through three proxies (or nodes). The key cryptographic challenge, here, is to establish symmetric session keys using a secure key exchange between the anonymous users and the selected nodes. The Tor network currently employs a one-way authenticated key exchange (1W-AKE) protocol 'ntor' for this purpose. Nevertheless, ntor as well as other known 1W-AKE protocols rely solely on some classical Diffie-Hellman (DH) type assumptions for their (forward) security, and thus privacy of Today's anonymous communication could not be ensured once quantum computers arrive. In this paper, we demonstrate utility of quantum-secure lattice-based cryptography towards solving this problem for onion routing. In particular, we present a novel hybrid 1W-AKE protocol (HybridOR) that is secure under the lattice-based ring learning with error (ring-LWE) assumption as well as the gap DH assumption. Due to its hybrid design, HybridOR is not only resilient against quantum attacks but also at the same time allows the OR nodes to use the current DH public keys and subsequently requires no modification to the the current Tor public key infrastructure. Moreover, thanks to the recent progress in lattice-based cryptography in the form of efficient ring-based constructions, our protocol is also computationally more efficient than the currently employed 1W-AKE protocol ntor, and it only introduces small and manageable communication overhead to the Tor protocol.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACNS 2015
TorOnion routingOne-way authenticated key exchangeLattice-based cryptographyLearning with errorGap Diffie-Hellman
Contact author(s)
satrajitgh @ gmail com
2015-06-05: last of 3 revisions
2015-01-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Satrajit Ghosh and Aniket Kate},
      title = {Post-Quantum Forward-Secure Onion Routing (Future Anonymity in Today’s Budget)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/008},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.