Ring learning with errors: Difference between revisions

Revision as of 01:15, 30 June 2015

Revision as of 23:25, 2 July 2015

Line 20:

=== The RLWE Problem ===

The RLWE problem can be stated in two different ways. One is called the "Search" variantversion and the other is the "Decision" Variantversion." The Search can be stated as follows. Let

* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>Z_q[x]/\Phi(x)</math> with coefficients from all of <math>F_q</math>.

* <math>e_i(x)</math> be a set of small random and '''unknown''' polynomials relative to a bound <math>b</math> in the ring <math>Z_q[x]/\Phi(x)</math>

Line 27:

<nowiki> </nowiki>Given the list of polynomial pairs <math>( a_i(x), b_i(x) )</math> find the unknown polynomial <math>s(x)</math>

Using the same definitions, the Decision Variantversion 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 characterized 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 intractableinfeasible 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�nding a short non-zero vector in alattice associated with an ideal in the polynomial

short non-zero vector in a lattice associated to an ideal in a cyclotomic ring. 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 ===