Ring learning with errors: Difference between revisions

Revision as of 23:25, 2 July 2015

Revision as of 02:19, 3 July 2015

Line 29:

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>Z_q[x]/\Phi(x)</math> with coefficients from all of <math>F_q</math>.

The difficulty of this problem is characterizedparameterized 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>). 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>Z_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 <math>s(x)</math>

=== Security Reduction ===

The difficulty of solving the RLWE problem is believed to be related to the difficulty of fi�ndingfinding a short non-zero vector in alatticea lattice associated with the polynomial ring <math>Z_q[x]/\Phi(x)</math> . In particular it is related to the difficulty of finding a vector shorter than an idealinteger α times the length of the shortest vector in the lattice where α is constrained to be a polynomial function of the degree n.

short non-zero vector in a lattice associated to an ideal in a cyclotomic ring. E.g., the distinguishing

Lyubashevsky, Peikert, and Regev, present the security of the Ring Learning with Errors Problem as follows:

"Suppose that it is hard for polynomial-time quantum algorithms to approximate (the search version of) the shortest vector problem (SVP) in the worst case on ideal lattices in R to within a fixed poly(n) factor. Then any poly(n) number of samples drawn from the R-LWE distribution are pseudorandom to any polynomial-time (possibly quantum) attacker."<ref>{{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>

E.g., the distinguishing

attack from [39] requires a short vector of a certain length to achieve a given

distinguishing advantage. Hence, parameters for R-LWE-based schemes are chosen such that