Ring learning with errors: Difference between revisions

Revision as of 18:55, 3 July 2015

Revision as of 20:30, 3 July 2015

Line 32:

=== Security Reduction ===

In cases where the polynomial <math>\Phi(x)</math> 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 <math>Z[x]/\Phi(x)</math> represented as integer vectors.<ref name=":0">{{Cite journal|title = On Ideal Lattices and Learning with Errors Over Rings|url = http://eprint.iacr.org/2012/230|date = 2012|first = Vadim|last = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev}}</ref> This problem is commonly known as the [[Shortest vector problem|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."<ref name=":0" />

TheirIn that quote, The ring R is <math>Z[x]/\Phi(x)</math> and theirthe ring R_q is <math>Z_q[x]/\Phi(x)</math>.

The average α-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" />

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" />

=== RLWE Cryptography ===