4.10 Short Invertible Polynomial Ring Elements

Let $R=\mathbb{Z}[X]/({\mathrm{\Phi }}_{\mathrm{\ell }}(X))$ and $R_q={\mathbb{Z}}_q[X]/({\mathrm{\Phi }}_{\mathrm{\ell }}(X))$. The factorization of ${\mathrm{\Phi }}_{\mathrm{\ell }}$ modulo $q$ controls how much CRT structure is available in $R_q$. If ${\mathrm{\Phi }}_{\mathrm{\ell }}$ splits into a few irreducible factors, one obtains a partially splitting ring. This is useful for fast multiplication and for constructing large challenge sets whose nonzero differences remain invertible [LS18].

For an integer $m>1$, write

such that $m=\phi (m)/\phi (\delta (m))\times \delta (m)$, and

For $a\in {\mathbb{Z}}_m^{\ast }$,

The paper also writes $s_1(m)$ for the largest singular value of the Vandermonde matrix associated with the primitive $m$-th roots of unity. We only need $\phi$ and $\mathrm{𝗈𝗋𝖽}$ for the splitting theorem below; $s_1$ appears in the later bounds showing that small elements are invertible.

The cyclotomic polynomial ${\mathrm{\Phi }}_m$ is fully splitting modulo $q$ if it factors into linear terms over ${\mathbb{Z}}_q$:

where the $r_j\in {\mathbb{Z}}_q^{\ast }$ are exactly the primitive $m^{\mathrm{th}}$ roots of unity modulo $q$, such that ${\mathrm{𝗈𝗋𝖽}}_q(r_j)=\phi (m)$. Since ${\mathbb{Z}}_q^{\ast }$ is cyclic of order $q-1$, this happens exactly when ${\mathbb{Z}}_q$ contains primitive $m^{\mathrm{th}}$ roots of unity, namely

In this case the CRT decomposes

The following theorem describes the characteristics of cyclotomic polynomial ring splitting, and more specifically, in the partial splitting case.

The condition $q\equiv 1modz$ means, there is a size $z$ multiplicative subgroup in ${\mathbb{Z}}_q^{\ast }$, such that $r_j$ are $z^{\mathrm{th}}$ primitive roots of unity, while ${\mathrm{𝗈𝗋𝖽}}_m(q)=m/z$ means, there is no elements in ${\mathbb{Z}}_q^{\ast }$ that $r_j$ can split to in the directions defined by the prime factors of $m/z$.

It is better to understand ${\mathrm{𝗈𝗋𝖽}}_m(q)$ in the Frobenius endomorphism aspect of view.

We then construct the minimal polynomial from a Frobenius orbit, which is irreducible over ${\mathbb{Z}}_q$.

If $\zeta$ is a $m^{\mathrm{th}}$ root of unity, ${\zeta }^{m/z}$ is a $z^{\mathrm{th}}$ root of unity. The primitiveness is preserved, say $\zeta$ is a primitive $m^{\mathrm{th}}$ root of unity, then ${\zeta }^{m/z}$ is a primitive $z^{\mathrm{th}}$ root of unity.

With ${\mathrm{𝗈𝗋𝖽}}_m(q)=m/z$, for a primitive $m^{\mathrm{th}}$ root of unity in ${\bar{\mathbb{Z}}}_q$, the Frobenius orbit has length $m/z$. By $q\equiv 1modz$, we know the $z^{\mathrm{th}}$ roots of unity are over ${\mathbb{Z}}_q$. Hence, for each primitive $m^{\mathrm{th}}$ root of unity $\zeta$, we have

where ${\zeta }^{m/z}=r$, and $r$ is a primitive $z^{\mathrm{th}}$ root of unity. Therefore, the $m/z$ long Frobenius orbit vanishes over $X^{m/z}-r_j$ that is irreducible over ${\mathbb{Z}}_q$ for all $j\in [1,\phi (z)]$.

The choice of $z$ controls the splitting pattern: the ring has $\phi (z)$ CRT slots, each tied to an extension field of degree $m/z$ over ${\mathbb{Z}}_q$. The fully splitting case is when $z=m$, where ${\mathrm{𝗈𝗋𝖽}}_m(q)=1$, namely $q\equiv 1modm$, then

By CRT decomposition, evaluation at these roots gives the NTT isomorphism. Let $n=\phi (m)$, then

and multiplication in $R_q$ becomes coordinate-wise multiplication after applying the NTT. In the power-of-two case $R=\mathbb{Z}[X]/(X^n+1)=\mathbb{Z}[X]/({\mathrm{\Phi }}_{2n}(X))$, this condition becomes $q\equiv 1mod2n$, so $X^n+1$ has all of its roots in ${\mathbb{Z}}_q$.

Let $R_m=\mathbb{Z}[X]/({\mathrm{\Phi }}_m(X))$ and let ${\omega }_1,\mathrm{\dots },{\omega }_{\phi (m)}$ be the primitive $m^{\mathrm{th}}$ roots of unity defined over complex field. The short-invertibility question in [LS18] is whether a nonzero short element of $R_{m,q}$ can vanish in one of the CRT coordinates induced by the above splitting. Suppose

where the $f_j$ are irreducible over ${\mathbb{Z}}_q$, then

and $y\in R_{m,q}$ is invertible when $y\not\equiv 0mod{f}_j(X)$ for every irreducible $f_j$. Hence, non-invertibility means that $y$ lands in the kernel of at least one CRT projection, and [LS18] views such kernels as ideal lattices under the canonical embedding. For $𝐲={\sum }_{i\in [0,\phi (m)-1]}{y}_i{X}^i\in R_m$, the canonical embedding is the complex evaluation vector

and the embedding norm is

Let $V_m$ be the associated Vandermonde matrix

The parameter $s_1(m)$ defined as

is the largest singular value of $V_m$, which is used to compare coefficient size with embedding size:

where $𝐲=(y_0,\mathrm{\dots },y_{\phi (m)-1})$ is the coefficient vector of $𝐲$.

We now construct the main result of [LS18] from the lower bound of embedding norm of an ideal lattice.

Consider $\mathrm{\Lambda }=\{𝐱\in R_m:𝐱\equiv 0mod(f_i,q)\}$, and the next result is immediate by lemma 4.10.4. First, $\mathrm{\Lambda }$ itself is an additive subgroup of ${\mathbb{Z}}^{\phi (m)}$. Second, for any $a\in \mathrm{\Lambda }$ and $b\in R_m$, we have $ab\in \mathrm{\Lambda }$. Hence, $\mathrm{\Lambda }$ is an ideal lattice.

Since $det(\mathrm{\Lambda })=\left|{\mathbb{Z}}^{\phi (m)}/\mathrm{\Lambda }\right|=q^{\phi (m)/d}$, then lemma 4.10.5 is immediate.

If a nonzero $𝐲$ vanishes in one CRT coordinate, then $𝐲$ lies in $\mathrm{\Lambda }$, and lemma 4.10.5 forces ${\Vert 𝐲\Vert }_2$ to be large. Thus any nonzero $𝐲$ whose coefficient norm is below this lower bound cannot vanish in any CRT coordinate.

Informally, short nonzero elements do not wrap around to zero in any NTT coordinate.