The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer.
RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices.
These problems are the difficulty of factoring the product of two carefully chosen prime numbers, the difficulty to compute discrete logarithms in a carefully chosen finite field, and the difficulty of computing discrete logarithms in a carefully chosen elliptic curve group.
If a quantum computer of sufficient size were built, all of the public key algorithms based on these three classically hard problems would be insecure.
One class of quantum resistant cryptographic algorithms is based on a concept called "learning with errors" introduced by Oded Regev in 2005.
[1] A specialized form of Learning with errors operates within the ring of polynomials over a finite field.
Like Diffie–Hellman and Elliptic Curve Diffie–Hellman, the Ring-LWE key exchange provides a cryptographic property called "forward secrecy"; the aim of which is to reduce the effectiveness of mass surveillance programs and ensure that there are no long term secret keys that can be compromised that would enable bulk decryption.
The security of the protocol is proven based on the hardness of solving the LWE problem.
The "New Hope" implementation[4] selected for Google's post-quantum experiment,[5] uses Peikert's scheme with variation in the error distribution.
For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.
An RLWE version of the classic MQV variant of a Diffie–Hellman key exchange was later published by Zhang et al. in 2014.
The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.
This article will closely follow the RLWE work of Ding in "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem".
[6][7] The RLWE-KEX uses polynomials which are considered "small" with respect to a measure called the "infinity norm."
The algorithm's security depends on an ability to generate random polynomials which are small with respect to the infinity norm.
The methods of reconciliation and key string generation depends on the specific RLWE-KEX scheme in question.
Following the guidance given in Peikert's paper, Singh suggested two sets of parameters for the RLWE-KEX.
In their November 2015 paper, Alkim, Ducas, Pöppelmann, and Schwabe recommend the following parameters n = 1024, q =12289, and
[11] This represents a 70% reduction in public key size over the n = 1024 parameters of Singh, and was submitted to NIST's Post-Quantum Cryptography Standardization project under the name NewHope.
Also in their November 2015 paper, Alkim, Ducas, Pöppelmann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a "nothing up my sleeve" or NUMS technique.
[11] An example of parameters generated in this way are the prime numbers for the Internet Key Exchange (RFC 2409) which embed the digits of the mathematical constant pi in the digital representation of the prime number.
[12] Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves.
[13] The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.
The security of this key exchange is based on the underlying hardness of ring learning with errors problem that has been proven to be as hard as the worst case solution to the shortest vector problem (SVP) in an ideal lattice.
[14] According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.
based on his work and others published in "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem.
[6] A variant of the approach described above is an authenticated version in the work of Zhang, Zhang, Ding, Snook and Dagdelen in their paper, "Post Quantum Authenticated Key Exchange from Ideal Lattices.
"[16] The concept of creating what has been called a Diffie–Hellman-like Key Exchange using lattices with a reconciliation function appears to have first been presented by French researchers Aguilar, Gaborit, Lacharme, Schrek, and Zemor at PQCrypto 2010 in their talk, "Noisy Diffie–Hellman Protocols.
"[17] In November 2015, Alkim, Ducas, Pöppelmann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters.
[11] Software based on the work of Alkim, Ducas, Pöppelmann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope[11]