Ring learning with errors: Difference between revisions

Revision as of 22:37, 3 July 2015

Revision as of 22:51, 3 July 2015

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.<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 [[discrete logarithm]] problem have served as the base for public key cryptography since the early 1980's.<ref>{{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|language = en|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 ismay be reducible to the NP-Hard [[Shortest vector problem|Shortest Vector Problem]] (SVP) in a Lattice.<ref name=":0" Hence/> a solution to the RLWE problem would imply a solution to a whole class of presumed hard computational problems.

=== Background ===

Line 9:

<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> .<ref name=":0" />

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.

Line 38:

In that quote, The ring R is <math>Z[x]/\Phi(x)</math> and the ring R_q is <math>Z_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" /> 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''."<ref>{{Cite web|title = What does GCHQ's “cautionary tale” mean for lattice cryptography?|url = http://www.cc.gatech.edu/~cpeikert/soliloquy.html|website = www.cc.gatech.edu|accessdate = 2015-07-03}}</ref>

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 ."<ref>{{Cite journal|title = Sieving for Shortest Vectors in Ideal Lattices|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider}}</ref> The difficult of these problems on regular lattices is provably [[NP-hard]].<ref name=":1" /> There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.<ref>{{Cite web|title = cr.yp.to:

2014.02.13: A subfield-logarithm attack against ideal lattices|url = http://blog.cr.yp.to/20140213-ideal.html|website = blog.cr.yp.to|accessdate = 2015-07-03}}</ref>

=== RLWE Cryptography ===