Ring learning with errors

The security of modern cryptography, in particular public-key cryptography, is based on the assumed intractability of solving certain computational problems if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly. The classic example that has been used since the 1970s is the integer factorization problem. It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random. As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. 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. == The RLWE problem ==

The RLWE problem can be stated in two different ways: a "search" version and a "decision" version. Both begin with the same construction. Let • a_i(x) be a set of random but known polynomials from \mathbf{F}_q[x]/\Phi(x) with coefficients from all of \mathbf{F}_q. • e_i(x) be a set of small random and unknown polynomials relative to a bound b in the ring \mathbf{F}_q[x]/\Phi(x). • s(x) be a small unknown polynomial relative to a bound b in the ring \mathbf{F}_q[x]/\Phi(x). • b_i(x) = (a_i(x)\cdot s(x)) + e_i(x). The Search version entails finding the unknown polynomial s(x) given the list of polynomial pairs ( a_i(x), b_i(x) ). The Decision version of the problem can be stated as follows. Given a list of polynomial pairs ( a_i(x), b_i(x) ), determine whether the b_i(x) polynomials were constructed as b_i(x) = (a_i(x)\cdot s(x)) + e_i(x) or were generated randomly from \mathbf{F}_q[x]/\Phi(x) with coefficients from all of \mathbf{F}_q. The difficulty of this problem is parameterized by the choice of the quotient polynomial (\Phi(x)), its degree (n), the field (\mathbf{F}_q), and the smallness bound (b). In many RLWE based public key algorithms the private key will be a pair of small polynomials s(x) and e(x). The corresponding public key will be a pair of polynomials a(x), selected randomly from \mathbf{F}_q[x]/\Phi(x), and the polynomial t(x)= (a(x)\cdot s(x)) + e(x). Given a(x) and t(x), it should be computationally infeasible to recover the polynomial s(x). == Security reduction ==

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 \mathbf{Z}[x]/\Phi(x) represented as integer vectors. This problem is commonly known as the Approximate Shortest Vector Problem (α-SVP) and it is the problem of finding a vector shorter than α times the shortest vector. The authors of the proof for this equivalence write: :"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in \mathbf{R} to the search version of ring-LWE, where the goal is to recover the secret s \in \mathbf{R}_q (with high probability, for any s) from arbitrarily many noisy products." However, there is not yet a proof to show that the difficulty of the α-SVP for ideal lattices is equivalent to the average α-SVP. Rather we have a proof that if there are any α-SVP instances that are hard to solve in ideal lattices then the RLWE Problem will be hard in random instances. The difficulty of these problems on regular lattices is provably NP-hard. 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). == RLWE cryptography ==

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. RLWE keys are roughly the square root of keys in LWE. The corresponding LWE scheme would require public keys of 49 million bits for the same level of security. Three groups of RLWE cryptographic algorithms exist: Ring learning with errors key exchanges (RLWE-KEX) 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 appeared in 2012 after a provisional patent application was filed in 2012. In 2014, Peikert 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. The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice. Ring learning with errors signature (RLWE-SIG) A RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital signature in 2011 by Lyubashevsky. 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." 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. Ring learning with errors homomorphic encryption (RLWE-HOM) Homomorphic encryption is type of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The purpose of homomorphic encryption is to allow the computations on sensitive data to occur on computing devices that should not be trusted with the data. 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. ==References==