I was reading some papers on Ring-LWE. I found almost all of them talk to choose the polynomial modulo $x^n+1$ where $n$ is a power of $2$. I did not understand why this condition is necessary?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
As @Raoul722 pointed out the polynomial should be irreducible.
One should also add the fact that in the original Ring-LWE article security proofs hold by sampling the error with a spherical distribution and the poly $f=x^{2^n}+1$.
In How (Not) to Instantiate Ring-LWE, from Invulnerability instantiations subsection it's specified that you could in fact select any number field and still be a hard problem but then you have to change the error distribution.
To answer your question, the reason is just to make proofs easier.
$\begingroup$
$\endgroup$
2
Definition: An element $\alpha$ in a finite field $F_q$ is called a primitive element (or generator) of $F_q$ if $F_q =\{0,\alpha,\alpha^2,...,\alpha^{q-1}\}$.
Let $\alpha$ be an element of $F_{q^m}$ then $\alpha$ is a root of $x^{q^m} − x=x(x^{q^m-1} − 1)$, so, this polynomial is a good tool for extending fields.
Also, choosing $x^n+1$ make modular operation so easy.
For example if $m\geq n$ then $$x^m =x^n\cdot x^{m-n}=-x^{m-n}\pmod {x^n+1}$$ So, using simple shift we can compute the remainder of polynomials module that.
answered May 27 '16 at 10:41
-
$\begingroup$ Can you please explain how did you get negative sign in describing modular exponentiation. $\endgroup$ – Node.JS Dec 1 '16 at 17:58
-
$\begingroup$ @Node.JS, I'm sorry. First negative sign is wrong but second is true. Thanks for your attention. I edit it. $\endgroup$ – Meysam Ghahramani Dec 1 '16 at 18:18
$\begingroup$
$\endgroup$
As wrote on Wikipedia
the security parameter $n$ is a power of $2$, making $f(x)$ irreducible over the rationals
Irreducible polynomials are widely used in cryptography: to construct finite fields for example.
