Ring learning with errors: Difference between revisions

Revision as of 19:58, 2 February 2016

Revision as of 19:07, 3 February 2016

Line 1:

{{technical|date=September 2015}}

'''Ring Learning with Errors (RLWE)''' is a [[computational problem]] which serves as the foundation of new cryptographic [[algorithm]]s 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.<ref name=":0" /> 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 [[→discretediscrete logarithm]] problem have served as the base for public key cryptography since the early 1980s.<ref name=":2">{{Cite book|title = Lattice Cryptography for the Internet|url = http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197–219|series = Lecture Notes in Computer Science|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca}}</ref> 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|NP-Hard]] [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice.<ref name=":0" />

== Background ==

Line 12:

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">\mathbf{Z}/q\mathbf{Z} = \mathbf{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 forms an infinite [[polynomial ring]] (<math display="inline">\mathbf{F}_q[x]</math>).<ref>{{Cite journal|title = Polynomial ring|url = https://en.wikipedia.org/w/index.php?title=Polynomial_ring&oldid=661646453|date = 2015}}</ref> 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 display="inline">\mathbf{F}_q[x]</math> modulo an [[irreducible polynomial]] <math display="inline">\Phi(x)</math>. This finite quotient ring can be written as <math>\mathbf{F}_q[x]/\Phi(x)</math> though many authors write <math>\mathbf{Z}_q[x]/\Phi(x)</math> .<ref name=":0" />

If the degree polynomial <math>\Phi(x)</math> is <math display="inline">n</math>, the sub-ring becomes the ring of polynomials of degree less than <math>n</math> modulo <math>\Phi(x)</math> with coefficients from <math>\mathbf{F}_qF_q</math>. The values <math display="inline">n</math>, <math display="inline">q</math>, 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]].<ref>{{Cite journal|title = Norm (mathematics)|url = https://en.wikipedia.org/w/index.php?title=Norm_(mathematics)&oldid=667112150|date = 2015}}</ref> 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>\mathbf{FZ}_q[x]/\Phi(x)</math> and the generation of "small" polynomials . A random polynomial is easily generated by simply randomly sampling the <math>n</math> coefficients of the polynomial from <math>\mathbf{F}_q</math>, where <math>\mathbf{F}_q</math> is typically represented as the set <math>\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2\}</math>.

Randomly generating a "small" polynomial done by generating the coefficients of the polynomial from <math>\mathbf{F}_q</math> in a way that either guarantees or makes very likely small coefficients. There are two common ways to do this:

Line 25:

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

* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>\mathbf{FZ}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{F}_q</math>.

* <math>e_i(x)</math> be a set of small random and '''unknown''' polynomials relative to a bound <math>b</math> in the ring <math>\mathbf{FZ}_q[x]/\Phi(x)</math>

* <math>s(x)</math> be a small '''unknown''' polynomial relative to a bound <math>b</math> in the ring <math>\mathbf{FZ}_q[x]/\Phi(x)</math>.

* <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>

Given the list of polynomial pairs <math>( a_i(x), b_i(x) )</math> find the unknown polynomial <math>s(x)</math>

Using the same definitions, the Decision version of the problem can be stated as follows. Given a list of polynomial pairs <math>( a_i(x), b_i(x) )</math> determine whether the <math>b_i(x)</math> polynomials were constructed as <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> or were generated randomly from <math>\mathbf{FZ}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{F}_q</math>.

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

== Security Reduction ==

Line 41:

:''"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in <math>\mathbf{R}</math> to the search version of ring-LWE, where the goal is to recover the secret <math>s \in \mathbf{R}_q</math> (with high probability, for any <math>s</math>) from arbitrarily many noisy products."''<ref name=":0" />

In that quote, The ring <math>\mathbf{R}</math> is <math>\mathbf{Z}[x]/\Phi(x)</math> and the ring <math>\mathbf{R}_q</math> is <math>\mathbf{FZ}_q[x]/\Phi(x)</math>.

The α-SVP in regular lattices is known to be [[NP-hard]] due to work by Daniele Micciancio in 2001.<ref name=":1">{{Cite journal|title = The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant|url = http://epubs.siam.org/doi/abs/10.1137/S0097539700373039|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008–2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio}}</ref> 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.<ref name=":0" />