Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

USENIX Security Symposium

Post-quantum key exchange - a new hope.

Erdem Alkım, Léo Ducas, Thomas Pöppelmann, Peter Schwabe

Published Jan 1, 2015• 511 citations
OpenAlex

Abstract

Abstract. Earlier in 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation. Specif-ically, we propose new parameters and a better suited error distribu-tion, analyze the scheme's hardness against attacks by quantum com-puters in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lat-tice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a fac-tor of 8 in a portable C implementation and by more than a factor of 20 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing at-tacks.

Related papers

Post-Quantum Key Exchange From Learning With Errors Over Rings

Rohit Khera

This note describes a key exchange method based on the ring-LWE (RLWE) assumption. It builds upon several results, including Regev's landmark quantum reduction from certain worst case lattice problems (approx. GapSVP and SIVP) to random instances of the search variant of a particular learning problem (LWE). It also builds on the follow on work of Lyubashevsky, Peikert and Regev on the average case hardness of the RLWE search variant for polynomially bounded numbers of RLWE samples, along with novel applications of automorphism groups in number fields for a RLWE search to decision reduction (thereby demonstrating pseudorandomness of RLWE in these number fields). Subsequently, these results were adopted for the construction of Diffie-Hellman like key exchange methods by Peikert, and then by Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who proposed efficient variants of such protocols. Subsequent work by Peikert proposed another efficient variant, phrased as a key encapsulation method, incorporating a low bandwidth reconciliation technique allowing two parties to exactly agree on a uniformly distributed secret value from noisy RLWE instances. This was followed by a concrete instantiation with parameter sets by Bos, Costello, Naehrig, Stebila, followed by another instantiation by Alkim, Ducas, Poppelmann and Schwabe with the same ring polynomial but a smaller modulus and a different reconciliation method. Unlike most other public key cryptography based key exchange methods, it is believed that RLWE based key exchange would remain secure in the event that an adversary is able to build a quantum computer. This document is a product of the Crypto Forum Research Group (CFRG).

•Oct 24, 2017•0 citations

Integration of post-quantum cryptography in the TLS protocol (LWE Option)

Luís Da Costa

With the possibility of quantum computers making an appearance, possibly capable of breaking several well established and widespread crytposystems (especially those that implement public key cryptography), necessity has arisen to create new cryptographic algorithms which remain safe even against adversaries using quantum computers. Several algorithms based on different mathematical problems have been proposed which are considered to be hard to solve with quantum computers. In recent years, a new lattice-based mathematical problem called Learning With Errors (and its variant Ring - Learning With Errors) was introduced, and several cryptosystems based on this problem were introduced, some of which are becoming practical enough to compete with traditional schemes that have been used for decades. The primary focus in this work is the implementation of two Ring - Learning With Errors based schemes (one key exchange mechanism and one digital signature scheme) on the TLS protocol via the OpenSSL library as a way of checking their overall viability in real-world scenarios, by comparing them to classical schemes implementing the same functionalities.

•Jan 1, 2019•0 citations

Frodo

Joppe W. Bos, Craig Costello, Léo Ducas +5 more

Lattice-based cryptography offers some of the most attractive primitives believed to be resistant to quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of works have proposed instantiations of practical post-quantum key exchange protocols based on hard problems in ideal lattices, mainly based on the Ring Learning With Errors (R-LWE) problem. While ideal lattices facilitate major efficiency and storage benefits over their non-ideal counterparts, the additional ring structure that enables these advantages also raises concerns about the assumed difficulty of the underlying problems. Thus, a question of significant interest to cryptographers, and especially to those currently placing bets on primitives that will withstand quantum adversaries, is how much of an advantage the additional ring structure actually gives in practice. Despite conventional wisdom that generic lattices might be too slow and unwieldy, we demonstrate that LWE-based key exchange is quite practical: our constant time implementation requires around 1.3ms computation time for each party; compared to the recent NewHope R-LWE scheme, communication sizes increase by a factor of 4.7x, but remain under 12 KiB in each direction. Our protocol is competitive when used for serving web pages over TLS; when partnered with ECDSA signatures, latencies increase by less than a factor of 1.6x, and (even under heavy load) server throughput only decreases by factors of 1.5x and 1.2x when serving typical 1 KiB and 100 KiB pages, respectively. To achieve these practical results, our protocol takes advantage of several innovations. These include techniques to optimize communication bandwidth, dynamic generation of public parameters (which also offers additional security against backdoors), carefully chosen error distributions, and tight security parameters.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 24, 2016•321 citations

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

Joppe W. Bos, Craig Costello, Michael Naehrig +1 more

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.

•Jan 1, 2014•8 citations

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

Joppe W. Bos, Craig Costello, Michael Naehrig +1 more

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.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2015•333 citations

Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol

Jiqiang Liu, Lin Li, Saraswathy Rv +2 more

Error reconciliation is an important technique for learning with error (LWE) and ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain the core idea of error reconciliation, building key exchange over RLWE problem, implementation and real-world performance, and compare them comprehensively. We also analyse a LWE key exchange 'Frodo' that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (> 200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11× faster than BCNS15 and one key exchange execution only costs 0.07 ms on a four-year-old middle range CPU. Error reconciliation is 1.57× faster than BCNS15.

International Journal of High Performance Computing and Networking•Jan 1, 2019•0 citations
Abstract. Earlier in 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation. Specif-ically, we propose new parameters and a better suited error distribu-tion, analyze the scheme's hardness against attacks by quantum com-puters in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lat-tice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a fac-tor of 8 in a portable C implementation and by more than a factor of 20 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing at-tacks.
This note describes a key exchange method based on the ring-LWE (RLWE) assumption. It builds upon several results, including Regev's landmark quantum reduction from certain worst case lattice problems (approx. GapSVP and SIVP) to random instances of the search variant of a particular learning problem (LWE). It also builds on the follow on work of Lyubashevsky, Peikert and Regev on the average case hardness of the RLWE search variant for polynomially bounded numbers of RLWE samples, along with novel applications of automorphism groups in number fields for a RLWE search to decision reduction (thereby demonstrating pseudorandomness of RLWE in these number fields). Subsequently, these results were adopted for the construction of Diffie-Hellman like key exchange methods by Peikert, and then by Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who proposed efficient variants of such protocols. Subsequent work by Peikert proposed another efficient variant, phrased as a key encapsulation method, incorporating a low bandwidth reconciliation technique allowing two parties to exactly agree on a uniformly distributed secret value from noisy RLWE instances. This was followed by a concrete instantiation with parameter sets by Bos, Costello, Naehrig, Stebila, followed by another instantiation by Alkim, Ducas, Poppelmann and Schwabe with the same ring polynomial but a smaller modulus and a different reconciliation method. Unlike most other public key cryptography based key exchange methods, it is believed that RLWE based key exchange would remain secure in the event that an adversary is able to build a quantum computer. This document is a product of the Crypto Forum Research Group (CFRG).
With the possibility of quantum computers making an appearance, possibly capable of breaking several well established and widespread crytposystems (especially those that implement public key cryptography), necessity has arisen to create new cryptographic algorithms which remain safe even against adversaries using quantum computers. Several algorithms based on different mathematical problems have been proposed which are considered to be hard to solve with quantum computers. In recent years, a new lattice-based mathematical problem called Learning With Errors (and its variant Ring - Learning With Errors) was introduced, and several cryptosystems based on this problem were introduced, some of which are becoming practical enough to compete with traditional schemes that have been used for decades. The primary focus in this work is the implementation of two Ring - Learning With Errors based schemes (one key exchange mechanism and one digital signature scheme) on the TLS protocol via the OpenSSL library as a way of checking their overall viability in real-world scenarios, by comparing them to classical schemes implementing the same functionalities.
Lattice-based cryptography offers some of the most attractive primitives believed to be resistant to quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of works have proposed instantiations of practical post-quantum key exchange protocols based on hard problems in ideal lattices, mainly based on the Ring Learning With Errors (R-LWE) problem. While ideal lattices facilitate major efficiency and storage benefits over their non-ideal counterparts, the additional ring structure that enables these advantages also raises concerns about the assumed difficulty of the underlying problems. Thus, a question of significant interest to cryptographers, and especially to those currently placing bets on primitives that will withstand quantum adversaries, is how much of an advantage the additional ring structure actually gives in practice. Despite conventional wisdom that generic lattices might be too slow and unwieldy, we demonstrate that LWE-based key exchange is quite practical: our constant time implementation requires around 1.3ms computation time for each party; compared to the recent NewHope R-LWE scheme, communication sizes increase by a factor of 4.7x, but remain under 12 KiB in each direction. Our protocol is competitive when used for serving web pages over TLS; when partnered with ECDSA signatures, latencies increase by less than a factor of 1.6x, and (even under heavy load) server throughput only decreases by factors of 1.5x and 1.2x when serving typical 1 KiB and 100 KiB pages, respectively. To achieve these practical results, our protocol takes advantage of several innovations. These include techniques to optimize communication bandwidth, dynamic generation of public parameters (which also offers additional security against backdoors), carefully chosen error distributions, and tight security parameters.
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.
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.
Error reconciliation is an important technique for learning with error (LWE) and ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain the core idea of error reconciliation, building key exchange over RLWE problem, implementation and real-world performance, and compare them comprehensively. We also analyse a LWE key exchange 'Frodo' that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (> 200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11× faster than BCNS15 and one key exchange execution only costs 0.07 ms on a four-year-old middle range CPU. Error reconciliation is 1.57× faster than BCNS15.