[Crypto] Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

Solution 1:

Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one. Let $n > d > 1$ be powers of two such that $q$ is a prime and $q \equiv 1 + 2d \mod 4d$, then $X^n + 1$ splits into $d$ irreducible polynomials of the form $X^{n/d} + r_i$ modulo $q$ where $0 < r_i < q$ (see Corollary 1.2 in https://eprint.iacr.org/2017/523.pdf). Then you can use FFT to compute multiplication in $d$ levels, and then do it manually in the end. This can be as fast as full FFT (see e.g. https://eprint.iacr.org/2020/1397.pdf).

---

Solution 2:

Another alternative that can be viable in some scenarios is to use the usual FFT over $\mathbb{C}$ instead of the Number Theoretic Transform (NTT) over $\mathbb{Z}_q$.

This is what FHEW does, for example.

In this case, $\omega$ is simply the complex number $e^{-2\pi i / (2n)}$, which is independent of $q$. However, you are performing the multiplication $a \cdot a'$ over over $\mathbb{R}$ instead of $\mathbb{Z}_q$, so you have to round the result then perform the reduction mod $q$ by yourself.

Moreover, it is known that the result of a multiplication with FFT is not exact (the implementations just use an approximation of $e^{-2\pi i / (2n)}$ after all), so instead of obtaining $a\cdot a' \in R_q$, at the end, you get $a\cdot a' + e \in R_q$, where $e$ is some error. If $n$ and $q$ are small, then $e$ is also small. Then, because RLWE samples already have an error term added to them, you can simply assume that you got the result you want plus another noise term.

You can find a short discussion about this approach in Section 6.3 of DM15