Ring learning with errors: Difference between revisions

Revision as of 11:00, 29 June 2015

Revision as of 01:15, 30 June 2015

Line 20:

=== The RLWE Problem ===

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

The RLWE problem can be stated is several different ways. The decision variant or the RLWE problem tries to distinguish between two large sets, <math>S_0</math> and <math>S_1</math>, of ordered pairs of polynomials from <math>Z_q[x]/\Phi(x)</math> . A pair of polynomials in the set <math>S_0</math> is created by randomly generating a polynomial <math>a(x)</math> from <math>Z_q[x]/\Phi(x)</math> and a small polynomials <math>s(x)</math> and <math>e(x)</math> subject to a bound <math>b</math>. An ordered pair of polynomials is:

* <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>

* <math>s(x)</math> be a small '''unknown''' polynomial relative to a bound <math>b</math> in the ring <math>Z_q[x]/\Phi(x)</math>.

* <math>tb_i(x) =</math><math>a (a_i(x)\cdot s(x)) +e e_i(x)</math>.

<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 Variant 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>.

<math>(a(x), (a(x)\cdot s(x))+e(x) )</math> and the set of ordered pairs can be indexed by i and becomes

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 intractable to recover <math>s(x)</math>

<math>S_0 = (a_i(x), (a_i(x)\cdot s_i(x))+e_i(x))</math> for i = 0 to z

The second set of ordered pairs of polynomials <math>S_1</math> is created by randomly generating two polynomials <math>a(x)</math> and <math>b(x)</math> from <math>Z_q[x]/\Phi(x)</math>, neither of which is small. This set can also be indexed by i and becomes:

<math>S_1 = (a_i(x), b_i(x))</math> for i = 0 to z

The Ring Learning with Errors Problem is the problem of distinguishing between set <math>S_0</math> and set <math>S_1</math> as z goes to <math>\infty</math>.

The more useful definition for RLWE in a cryptographic context is as follows. Given polynomials <math>a(x)</math> and <math>t(x)</math> from <math>Z_q[x]/\Phi(x)</math> find "small" polynomials <math>s(x)</math> and <math>e(x)</math> subject to a bound <math>b</math> in <math>Z_q[x]/\Phi(x)</math> such that:

<math>t(x) =</math><math>a(x)\cdot s(x)+e(x)</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>).

=== Security Reduction ===