Post-quantum key exchange for the TLS protocol from the ring learning with errors problem

01.10.2015, 15:00 – 16:30

2015/10/01 15:00-16:30

Speaker: Douglas Stebila | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Marc Fischlin


In this talk I'll discuss a recent research project on designing and implementing post-quantum key exchange from the ring learning with errors problem in the TLS protocol. In this first part of the talk, I'll give background on the ring learning with errors problem, discuss the design and security of the key exchange algorithm, and talk about the performance when integrated into TLS. In the second part of the talk, I'll talk about how to actually work with OpenSSL and Apache, going through some of the process of adding a new primitive to OpenSSL's libcrypto, integrating that into a new ciphersuite in libssl, and testing performance using Apache and http_load.

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem; we accompany these ciphersuites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using RSA or elliptic curve digital signatures: the post-quantum key exchange provides forward secrecy against future quantum attackers, while authentication can be provided using RSA keys that are issued by today's commercial certificate authorities, smoothing the path to adoption.

Our cryptographically secure implementation, aimed at the 128-bit security level, reveals that the performance price when switching from non-quantum-safe key exchange is not too high. With our R-LWE ciphersuites integrated into the OpenSSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10 KiB payload. Compared to elliptic curve Diffie--Hellman, this means an 8 KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that post-quantum key-exchange can already be considered practical. Paper and implementation available from

Joint work with Joppe W. Bos (NXP Semiconductors) and Craig Costello and Michael Naehrig (Microsoft Research).

Short Bio

Dr. Douglas Stebila is a Senior Lecturer in cryptography at the Queensland University of Technology in Brisbane, Australia. His research focuses on improving the security of Internet cryptography protocols such as SSL/TLS and SSH. His previous work on the integration and standardization of elliptic curve cryptography in SSL/TLS has been deployed on hundreds of millions of web browsers and servers worldwide. He holds an MSc from the University of Oxford and a PhD from the University of Waterloo.