Ring learning with errors: Difference between revisions

Revision as of 14:40, 8 September 2015

Revision as of 23:07, 16 September 2015

Line 29:

* <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>b_i(x) = (a_i(x)\cdot s(x)) + 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 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>.