Ring learning with errors

Ring Learning with Errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. RLWE is more properly called Learning with Errors over Rings and is simply the larger Learning with Errors 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 1980's.^[2] An important feature of basing cryptography on the Ring Learning with Errors problem is the fact that the solution to the RLWE problem may be reducible to the NP-Hard Shortest Vector Problem (SVP) in a Lattice.^[1]

Background

The security of modern cryptography, in particular Public Key Cryptography, is based on the difficulty of solving computational problems believed to be intractable 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 1970's 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. A typical polynomial a(x) is expressed as:

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$ 

Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field ${\textstyle Z/qZ=F_{q}}$  for a prime integer ${\textstyle q}$ . The set of polynomials over a finite field with the operations of addition and multiplication for an infinite polynomial ring (${\displaystyle F_{q}[x]}$ ). The RLWE context works with a finite sub-ring of this infinite ring. The sub-ring is typically the finite quotient (factor) ring formed by reducing all of the polynomials in ${\displaystyle F_{q}[x]}$  modulo an irreducible polynomial ${\displaystyle \Phi (x)}$ . This finite quotient ring can be written as ${\displaystyle F_{q}[x]/\Phi (x)}$  though many authors write ${\displaystyle Z_{q}[x]/\Phi (x)}$  .^[1]

If the degree polynomial ${\displaystyle \Phi (x)}$  is n, the sub-ring becomes the ring of polynomials of degree less than n modulo ${\displaystyle \Phi (x)}$  with coefficients from ${\displaystyle F_{q}}$ . The values n, q, together with the polynomial ${\displaystyle \Phi (x)}$  partially define the mathematical context for the RLWE problem.

Another concept necessary for the RLWE problem is the idea of "small" polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the infinity norm. The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, ${\displaystyle ||a(x)||_{\infty }=b}$  states that the infinity norm of the polynomial ${\displaystyle a(x)}$  is ${\displaystyle b}$ . Thus ${\displaystyle b}$  is the largest coefficient of ${\displaystyle a(x)}$ .

The final concept necessary to understand the RLWE problem is the generation of random polynomials in ${\displaystyle Z_{q}[x]/\Phi (x)}$  . This is easily done by simply randomly sampling the n coefficients of the polynomial from ${\displaystyle F_{q}}$  where ${\displaystyle F_{q}}$  is typically represented as the set:${\displaystyle (-(q-1)/2,...,-1,0,1,...,(q-1)/2)}$ .

To randomly generate a "small" polynomial we select a bound for the infinity norm, ${\displaystyle b<<q}$  and then randomly sample the n coefficients from the set: ${\displaystyle (-b,...,-1,0,1,...,b)}$ . A typical value for ${\displaystyle b}$  is 1, so the coefficients are simply chosen from -1, 0, and 1.

The RLWE Problem

The RLWE problem can be stated in two different ways. One is called the "Search" version and the other is the "Decision" version. The Search can be stated as follows. Let

• ${\displaystyle a_{i}(x)}$  be a set of random but known polynomials from ${\displaystyle Z_{q}[x]/\Phi (x)}$  with coefficients from all of ${\displaystyle F_{q}}$ .
• ${\displaystyle e_{i}(x)}$  be a set of small random and unknown polynomials relative to a bound ${\displaystyle b}$  in the ring ${\displaystyle Z_{q}[x]/\Phi (x)}$ 
• ${\displaystyle s(x)}$  be a small unknown polynomial relative to a bound ${\displaystyle b}$  in the ring ${\displaystyle Z_{q}[x]/\Phi (x)}$ .
• ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$ 

Given the list of polynomial pairs ${\displaystyle (a_{i}(x),b_{i}(x))}$  find the unknown polynomial ${\displaystyle s(x)}$ 

Using the same definitions, the Decision version of the problem can be stated as follows. Given a list of polynomial pairs ${\displaystyle (a_{i}(x),b_{i}(x))}$  determine whether the ${\displaystyle b_{i}(x)}$  polynomials were constructed as ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$  or were generated randomly from ${\displaystyle Z_{q}[x]/\Phi (x)}$  with coefficients from all of ${\displaystyle F_{q}}$ .

The difficulty of this problem is parameterized by the choice of the quotient polynomial ( ${\displaystyle \Phi (x)}$  ), its degree (n), the field (${\displaystyle F_{q}}$ ), and the smallness bound (${\displaystyle b}$ ). In many RLWE based public key algorithms the private key will be a pair of small polynomials ${\displaystyle s(x)}$  and ${\displaystyle e(x)}$ . The corresponding public key will be a pair of polynomials ${\displaystyle a(x)}$ , selected randomly from ${\displaystyle Z_{q}[x]/\Phi (x)}$ , and the polynomial ${\displaystyle t(x)=(a(x)\cdot s(x))+e(x)}$ . Given ${\displaystyle a(x)}$  and ${\displaystyle t(x)}$ , it should be computationally infeasible to recover the polynomial ${\displaystyle s(x)}$ 

Security Reduction

In cases where the polynomial ${\displaystyle \Phi (x)}$  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 ${\displaystyle Z[x]/\Phi (x)}$  represented as integer vectors.^[1] 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 R to the search version of ring-LWE, where the goal is to recover the secret s ∈ R_q (with high probability, for any s) from arbitrarily many noisy products."^[1]

In that quote, The ring R is ${\displaystyle Z[x]/\Phi (x)}$  and the ring R_q is ${\displaystyle Z_{q}[x]/\Phi (x)}$ .

The α-SVP in regular lattices is known to be NP-hard due to work by Daniele Micciancio in 2001.^[3] 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. ^[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. It is widely believed that solving SVP (and all other lattice problems) in ideal lattices is as hard as in regular lattices ."^[4] The difficulty of these problems on regular lattices is provably NP-hard.^[3] There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.^[5]

These security equivalences make the RLWE problem a good basis for future cryptography. Chris Peikert, one of the authors of the proof of this security reduction, states the following: "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).^[6]

RLWE Cryptography 

Cryptography based on the RLWE problem is very efficient both when compared with cryptography based on its parent problem, Learning with Errors, and compared with current public key algorithms like the RSA, Diffie-Hellman and Elliptic Curve Diffie-Hellman algorithms.

1. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2012). "On Ideal Lattices and Learning with Errors Over Rings". {{cite journal}}: Cite journal requires |journal= (help)
2. Peikert, Chris. Mosca, Michele (ed.). Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. pp. 197–219. ISBN 978-3-319-11658-7.
3. Micciancio, D. (January 1, 2001). "The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant". SIAM Journal on Computing. 30 (6): 2008–2035. doi:10.1137/S0097539700373039. ISSN 0097-5397.
4. Schneider, Michael (2011). "Sieving for Shortest Vectors in Ideal Lattices". {{cite journal}}: Cite journal requires |journal= (help)
5. "cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices". blog.cr.yp.to. Retrieved 2015-07-03. {{cite web}}: line feed character in |title= at position 11 (help)
6. "What does GCHQ's "cautionary tale" mean for lattice cryptography?". www.cc.gatech.edu. Retrieved 2015-07-03.