Content deleted Content added
m →[[Ring learning with errors key exchange|Ring Learning with Errors Key Exchanges]] (RLWE-KEX): Removed invisible unicode characters + other fixes, replaced: → (2) using AWB |
Clean up description of search and decision versions. |
||
Line 24:
== The RLWE Problem ==
The RLWE problem can be stated in two different ways
* <math>a_i(x)</math> be a set of random but '''known''' polynomials from <math>\mathbf{Z}_q[x]/\Phi(x)</math> with coefficients from all of <math>\mathbf{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>\mathbf{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>\mathbf{Z}_q[x]/\Phi(x)</math>.
* <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>
The difficulty of this problem is parameterized by the choice of the quotient polynomial (<math>\Phi(x)</math>), its degree (<math>n</math>), the field (<math>\mathbf{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>\mathbf{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>.
| |||