Paper 2015/287

A quantum-safe circuit-extension handshake for Tor

John Schanck and William Whyte and Zhenfei Zhang

Abstract

We propose a method for integrating NTRUEncrypt into the ntor key exchange protocol as a means of achieving a quantum-safe variant of forward secrecy. The proposal is a minimal change to ntor, essentially consisting of an NTRUEncrypt-based key exchange performed in parallel with the ntor handshake. Performance figures are provided demonstrating that the client bears most of the additional overhead, and that the added load on the router side is acceptable. We make this proposal for two reasons. First, we believe it to be an interesting case study into the practicality of quantum-safe cryptography and into the difficulties one might encounter when transitioning to quantum-safe primitives within real-world protocols and code-bases. Second, we believe that Tor is a strong candidate for an early transition to quantum-safe primitives; users of Tor may be justifiably concerned about adversaries who record traffic in the present and store it for decryption when technology or cryptanalytic techniques improve in the future.