Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem

By Joppe W. Bos, Craig Costello, Michael Naehrig, Douglas Stebila. IEEE Symposium on Security and Privacy, 2015

391 citations recorded by the source corpus.

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 cipher suites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem, we accompany these cipher suites 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 cipher suites integrated into the Open SSL 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 provably secure post-quantum key-exchange can already be considered practical.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/073840d59f4418ad52d6961763b227d0dc3ee582

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

Citations in the corpus

A Modular Analysis of the Fujisaki-Okamoto Transformation (2017, background): “Dealing with imperfectly correct schemes is of great importance since many (but not all) practical lattice-based encryption schemes have a small correctness error, see, e.g., DXL [21], Peikert [34], BCNS [14], New Hope [3], Frodo [13], Lizard [17], and Kyber [12].”
Post-quantum Key Exchange - A New Hope (2016, methodology): “In this section we briefly revisit the passively secure key-encapsulation mechanism (KEM) that was proposed by Peikert [71] and instantiated in [18] (BCNS).”
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (2016, background): “R-LWE-based schemes have been proposed for public-key encryption [35, 24, 28], digital signatures [22, 12], and key exchange [11, 28, 36, 6, 2].”
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, methodology): “’s proof of R-LWE DH key exchange [14].”