Red Pine on Wilderness Trail

Douglas Stebila

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

HTTPS connections per second supported by the server at 128-bit security level. All ciphersuites use AES-128-GCM and SHA256.
HTTPS connections per second supported by the server at 128-bit security level. All ciphersuites use AES-128-GCM and SHA256.

Abstract

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.

Keywords: cryptographic protocols, post-quantum, learning with errors, Transport Layer Security (TLS), key exchange

Reference

Joppe W. Bos, Craig Costello, Michael Naehrig, Douglas Stebila. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In Proc. IEEE Symposium on Security and Privacy (S&P) 2015, pp. 553-570. IEEE, May 2015. © IEEE.

Download

Code

  • C implementation of the core ring learning with errors key exchange protocol in the liboqs library: GitHub
  • Integration into OpenSSL 1.0.2 via liboqs: GitHub
  • DEPRECATED: C implementation of the core ring learning with errors key exchange protocol: GitHub (old repository)
  • DEPRECATED: Integration into OpenSSL 1.0.1: GitHub (be sure to use OpenSSL_1_0_1_stable branch), diff against OpenSSL 1.0.1f

Presentations

Media

BibTeX

Funding

This research was supported by:
  • Australian Research Council (ARC) Discovery Project grant DP130104304