In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption.
Public-key cryptography relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known.
RLWE is more properly called learning with errors over rings and is simply the larger learning with errors (LWE) problem specialized to polynomial rings over finite fields.
[1] Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for public-key cryptography in the future just as the integer factorization and discrete logarithm problem have served as the base for public key cryptography since the early 1980s.
Integer factorization forms the basis of the widely used RSA cryptographic algorithm.
The ring learning with errors (RLWE) problem is built on the arithmetic of polynomials with coefficients from a finite field.
is expressed as: Polynomials can be added and multiplied in the usual fashion.
Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm.
The final concept necessary to understand the RLWE problem is the generation of random polynomials in
Let The Search version entails finding the unknown polynomial
The difficulty of this problem is parameterized by the choice of the quotient polynomial (
is a cyclotomic polynomial, the difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest vector) in an ideal lattice formed from elements of
The authors of the proof for this equivalence write: In that quote, The ring
The α-SVP in regular lattices is known to be NP-hard due to work by Daniele Micciancio in 2001, although not for values of α required for a reduction to general learning with errors problem.
[1] Regarding the difficulty of Shortest Vector Problems in Ideal Lattices, researcher Michael Schneider writes, "So far there is no SVP algorithm making use of the special structure of ideal lattices.
[7] Peikert believes that these security equivalences make the RLWE problem a good basis for future cryptography.
He writes: "There is a mathematical proof that the only way to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in the worst case" (emphasis in the original).
[8] A major advantage that RLWE based cryptography has over the original learning with errors (LWE) based cryptography is found in the size of the public and private keys.
[9] The corresponding LWE scheme would require public keys of 49 million bits for the same level of security.
From a computational standpoint, however, RLWE algorithms have been shown to be the equal of or better than existing public key systems.
[10] Three groups of RLWE cryptographic algorithms exist: The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding.
The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security.
The paper[11] appeared in 2012 after a provisional patent application was filed in 2012.
In 2014, Peikert[12] presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized.
An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al.[13] The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.
A RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital signature in 2011 by Lyubashevsky.
[14] The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems.
"[15] These papers laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.
These computing devices are allowed to process the ciphertext which is output from a homomorphic encryption.
In 2011, Brakersky and Vaikuntanathan, published "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages" which builds a homomorphic encryption scheme directly on the RLWE problem.