When multiplying polynomials from $\mathbb{Z}_q[X] / (X^n-1) $, the discrete NTT is used because: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right) $$
However, in virtually all schemes I've seen the negacyclic convolution is used - the ring is $\mathbb{Z}_q[X] / (X^n+1) $ and a trick is used to compute $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) \right) $ using $\mathsf{NTT}_n$ because we have to multiply the polynomials in $\mathbb{Z}_q[X] / (X^{2n}-1) $.
My question is - why bother with $\mathbb{Z}_q[X] / (X^n+1) $ and not simply use $\mathbb{Z}_q[X] / (X^n-1) $, thus applying $\mathsf{NTT}_n$ in a straightforward way with no extra complications?
2 Answers
The underlying hard problem used to construct the cryptographic primitives requires us to use that ring of polynomials modulo $X^n + 1$.
For example, if the security of your scheme relies on RLWE, then you have to stick with the rings that make the RLWE secure, which means that you cannot use $X^n - 1$, as discussed in this answer.
You have the same situation for the Ring-SIS problem.
In general, you have to be careful when you instantiate any problem with $X^n - 1$ as the modulus, because one can evaluate the polynomials on $1$ to work over integers instead of polynomials. This is discussed, for example, in the section "Polynomial evaluation" of this paper.
You state (I have fixed your notation, residue classes are taken with a $/$ not $\backslash)$ the former is setminus which is not the same:
However, in virtually all schemes I've seen the negacyclic convolution is used - the ring is $\mathbb{Z}_q[X] / (X^n+1) $ and a trick is used to compute $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right) \right) $ using $\mathsf{NTT}_n$ because we have to multiply the polynomials in $\mathbb{Z}_q[X] / (X^{2n}-1) $.
and ask the question:
why bother with $\mathbb{Z}_q[X] / (X^n+1) $ and not simply use $\mathbb{Z}_q[X] \setminus (X^n-1) $?
If we have the polynomial factorization $x^{2n}-1=(x^n-1)(x^n+1)$ then computations modulo $x^{2n}-1$ can be speeded up by convolving (via NTT) with respect to each one of the factors and then combining. So
- We have a factorization that leads to a fast transform, so we take this route. The extreme case is complex FFT when we can factor all the way into linear factors $x^n-1=\prod_{i=1}^n (\omega^i-1)$ with $\omega$ a primitive $n^{th}$ root of unity.
- The factorization is unique, you cannot use $(x^n+1)$ only since $(x^n+1)^2=(x^{2n}+2 x^n+1)$ and $q$ is in general not characteristic 2. If you meant actually just use $x^{2n}-1$ directly, you'd have no speedup.
-
1$\begingroup$ Sorry, my bad with the quotient notation. I think you misunderstood my question (or I have misunderstood your answer). I'm not asking how to multiply polynomials of degree $(2n-1)$ using NTTs of order $n$, and am not asking why it's impossible to multiply polynomials from $\mathbb{Z}_q[X]/(X^n+1)$ with NTTs. I'm asking why use polynomials modolu $X^n+1$ in the first place (which need the trick with $(X^{2n}-1)$), and not use polynomials modolu $X^n-1$ $\endgroup$ Commented May 22, 2022 at 13:46
-
$\begingroup$ if your length is $N=2n,$ i.e., even, this IS the factorisation you must use to begin with i.e., $x^{2n}-1=(x^n-1)(x^n+1)$ because any $2n^{th}$ root of unity in any field or ring is either order $2n$ (those which are -1 when raised to power $n$) or have order dividing $n$. $\endgroup$– kodluCommented May 23, 2022 at 13:29
-