8
$\begingroup$

In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words:

Let $q$ be a prime and $n>4$ be a power of $2$. What is the cardinality of $K^*$?

$\endgroup$
0
3
$\begingroup$

The $n$th cyclotomic polynomial $\Phi_n\in\mathbb Z[x]$ is irreducible in $\mathbb F_q[x]$ if and only if $q$ is a generator of $(\mathbb Z/n)^\times$ (proof). Hence, unfortunately, the polynomial $x^n+1$ is never irreducible modulo $q$ if $n>4$ is a power of two: The group $(\mathbb Z/n)^\times$ is not cyclic in that case. Thus it may indeed happen that the polynomial chosen in NTRU is not invertible.

Since I am not aware of any exact results, we shall derive a generic lower bound for the cardinality of $(\mathbb F_q[x]/(x^n+1))^\times$. (By "generic", I mean that the following is not specific to cyclotomic polynomials. I suspect one can obtain much better bounds by using cyclotomic theory.)

I will assume $q\geq3$. Then the polynomial $x^n+1$ is square-free over $\mathbb F_q$ since $\gcd(x^n+1,nx^{n-1})=1$. Decompose $x^n+1$ into (therefore distinct) irreducible factors $g_i\in\mathbb F_q[x]$ of degrees $e_i:=\deg g_i$. By the Chinese remainder theorem, we have an isomorphism $$ \varphi\colon\quad \mathbb F_q[x]/(x^n+1) \;\cong\; \prod_{i=1}^r\underbrace{\mathbb F_q[x]/g_i}_{\cong\ \mathbb F_{q^{e_i}}} \text. $$ Composing this isomorphism with projections to the direct factors $\mathbb F_q[x]/g_i$ yields ring homomorphisms $$ \pi_i\colon\quad \mathbb F_q[x]/(x^n+1) \;\to\; \mathbb F_{q^{e_i}} $$ with the property that an element of $\mathbb F_q[x]/(x^n+1)$ is invertible if and only if its image under each $\pi_i$ is invertible, i.e., non-zero. Hence the probability that an element $f\in\mathbb F_q[x]/(x^n+1)$ chosen uniformly at random is a unit is $$ \Pr[\text{unit}] \;=\; \prod_{i=1}^r (1-1/q^{e_i}) \text. $$ How bad can this become? In the worst case, we have $r=n$ and all $e_i=1$, hence $$ \Pr[\text{unit}] \;\geq\; (1-1/q)^n \text. $$

When considering small $q$ and large $n$, this bound becomes quite low quickly, but keep in mind that it is a worst-case estimate. In practice, it seems that the $e_i$ are typically much greater than $1$.

Moreover, in the NTRU scenario, $q$ is quite big: The parameters recommended, depending on the source, are roughly $q\approx 2000$ and $n\approx 1000$, yielding $$ \Pr[\text{unit}] \;\geq\; \frac12 \text, $$ so one can easily find a unit within a few tries with very large probability.

$\endgroup$
2
$\begingroup$

This depends on the factorization of $X^n+1$ modulo $\mathbb{F}_q$.

If you have $X^n+1 = \prod_i f_i(X)^{e_i}$ with $f_i$ irreducible and $e_i>0$, then $K = \prod_i \mathbb{F}_q[X]/(f_i^{e_i})$ and $K^\times = \prod_i (\mathbb{F}_q[X]/(f_i^{e_i}))^\times$.

An element of $\mathbb{F}_q[X]/(f_i^{e_i})$ is invertible, iff it is invertible modulo $f_i[X]$. As $\mathbb{F}_q[X]/(f_i)$ is a field of order $q^{\deg f_i}$, you should get $|K^\times|/|K| = \prod_i (1-q^{-\deg f_i})$.

$\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.