Ring learning with errors: Difference between revisions

Revision as of 02:19, 3 July 2015

Revision as of 14:27, 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 parameterized 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 the polynomial <math>s(x)</math>

=== Security Reduction ===

The difficulty of solving the RLWE problem is believed to be related to the difficulty of finding a short non-zero vector in a 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 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.

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

polynomial run-time exponential-approximation algorithms such as LLL [31] are unlikely to

�nd such short vectors (cf. [52, 32]). The known algorithms which are capable of �nding exact

solutions to the lattice problem all have exponential run time.

=== RLWE Cryptography ===

__NOINDEX__