Content deleted Content added
←Blanked the page |
No edit summary |
||
Line 1:
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|Learning with Errors]] problem specialized to polynomial rings over finite fields. 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|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. An important feature of basing cryptography on the Ring Learning with Errors problem is the fact that the solution to the RLWE problem is reducible to the NP-Hard [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice. Hence a solution to the RLWE problem would imply a solution to a whole class of presumed hard computational problems.
=== 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 (cryptosystem)|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:
<math>a(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>
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 <math display="inline">Z/qZ = F_q</math> for a prime integer <math display="inline">q</math>. The set of polynomials over a finite field with the operations of addition and multiplication for an infinite [[polynomial ring]] (<math>F_q[x]</math>). The RLWE context works with a finite sub-ring of this infinite ring. The sub-ring is typically the finite [[Quotient ring|quotient (factor) ring]] formed by reducing all of the polynomials in <math>F_q[x]</math>modulo an [[irreducible polynomial]] <math>\Phi(x)</math>. This finite quotient ring can be written as <math>F_q[x]/\Phi(x)</math> though many authors write <math>Z_q[x]/\Phi(x)</math> .
If the degree polynomial <math>\Phi(x)</math> is n, the sub-ring becomes the ring of polynomials of degree less than n modulo <math>\Phi(x)</math> with coefficients from <math>F_q</math>. The values n, q, together with the polynomial <math>\Phi(x)</math> 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, <math>||a(x)||_\infty = b</math> states that the [[infinity norm]] of the polynomial <math>a(x)</math> is <math>b</math>. Thus <math>b</math> is the largest coefficient of <math>a(x)</math>.
The final concept necessary to understand the RLWE problem is the generation of random polynomials in <math>Z_q[x]/\Phi(x)</math> . This is easily done by simply randomly sampling the n coefficients of the polynomial from <math>F_q</math> where <math>F_q</math> is typically represented as the set:<math>(-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2)</math>.
To randomly generate a "small" polynomial we select a bound for the infinity norm, <math>b<<q</math> and then randomly sample the n coefficients from the set: <math>(-b, ..., -1, 0, 1, ..., b)</math>. A typical value for <math>b</math> is 1, so the coefficients are simply chosen from -1, 0, and 1.
=== The RLWE Problem ===
The RLWE problem can be stated is several different ways. The decision variant or the RLWE problem tries to distinguish between two large sets, <math>S_0</math> and <math>S_1</math>, of ordered pairs of polynomials from <math>Z_q[x]/\Phi(x)</math> . A pair of polynomials in the set <math>S_0</math> is created by randomly generating a polynomial <math>a(x)</math> from <math>Z_q[x]/\Phi(x)</math> and a small polynomials <math>s(x)</math> and <math>e(x)</math> subject to a bound <math>b</math>. An ordered pair of polynomials is:
<math>(a(x), (a(x)\cdot s(x))+e(x) )</math> and the set of ordered pairs can be indexed by i and becomes
<math>S_0 = (a_i(x), (a_i(x)\cdot s_i(x))+e_i(x))</math> for i = 0 to z
The second set of ordered pairs of polynomials <math>S_1</math> is created by randomly generating two polynomials <math>a(x)</math> and <math>b(x)</math> from <math>Z_q[x]/\Phi(x)</math>, neither of which is small. This set can also be indexed by i and becomes:
<math>S_1 = (a_i(x), b_i(x))</math> for i = 0 to z
The Ring Learning with Errors Problem is the problem of distinguishing between set <math>S_0</math> and set <math>S_1</math> as z goes to <math>\infty</math>.
The more useful definition for RLWE in a cryptographic context is as follows. Given polynomials <math>a(x)</math> and <math>t(x)</math> from <math>Z_q[x]/\Phi(x)</math> find "small" polynomials <math>s(x)</math> and <math>e(x)</math> subject to a bound <math>b</math> in <math>Z_q[x]/\Phi(x)</math> such that:
<math>t(x) =</math><math>a(x)\cdot s(x)+e(x)</math>.
The difficulty of this problem is characterized by the choice of the quotient polynomial ( <math>\Phi(x)</math> ), its degree (n), the field (<math>F_q</math>), and the smallness bound (<math>b</math>).
=== Security Reduction ===
=== RLWE Cryptography ===
| |||