4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.