Ring learning with errors: Difference between revisions

Revision as of 14:27, 3 July 2015

Revision as of 18:44, 3 July 2015

Line 32:

=== Security Reduction ===

TheIn cases where the polynomial <math>\Phi(x)</math> is a cyclotomic polynomial, the difficulty of solving the search version of RLWE problem is believedequivalent to befinding relateda toshort thevector difficulty(but ofnot findingnecessarily athe short non-zeroshortest) vector in aan ideal lattice associatedformed withfrom theelements polynomial ringof <math>Z_qZ[x]/\Phi(x)</math> .represented as Ininteger particularvectors.<ref itname=":0">{{Cite isjournal|title related= toOn the difficultyIdeal of findingLattices a vector shorterand than anLearning integer αwith times theErrors length ofOver the shortestRings|url vector= inhttp://eprint.iacr.org/2012/230|date the= lattice2012|first where= αVadim|last is= constrainedLyubashevsky|first2 to= beChris|last2 a= polynomialPeikert|first3 function= ofOded|last3 the= degree n.Regev}}</ref> 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."<ref name=":0" />

Their ring R is <math>Z[x]/\Phi(x)</math> and their R_q is <math>Z_q[x]/\Phi(x)</math>.

In particular it is related to the difficulty of finding a vector shorter than an integer α times the length of the shortest vector in the lattice where α is constrained to be a polynomial function of the degree n. This is known as the "Approximate Shortest Vector Problem."

Researchers have shown that if the Approximate Shortest Vector Problem is hard to solve in the worst case then the decision version of the Ring Learning with Errors problem will be hard to solve in an average case. In other words, if any instance of the Approximate Short Vector Problem is hard in the lattice, then the RLWE will be hard for random instances of the problem.