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

For RLWE (Ring Learning With Errors) scheme, we use $$R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$$ where $$n = 2^{d}$$ for some $$d$$. Since there exists $$2n$$-th root of unity in $$\mathbb{Z}_{q}$$ (which is the generator of the cyclic group $$\mathbb{Z}_{q}^{\times}$$), we can do FFT with the choice of the root of unity $$\omega$$ and do polynomial multiplication in $$O(n\log n)$$. Is there a way to apply FFT for primes $$q \neq 1\,(\mathrm{mod}\,2n)$$, so that there's no $$2n$$-th root of unity mod $$q$$?

• I think the title of the question and the contents are somehow different. Do you ask about the possibility of FFT in $R_q$, or about the security of RLWE with general modulus? For the latter, the security of RLWE is guaranteed for certain parameter regime, see e.g. eprint.iacr.org/2017/258.pdf
– Hhan
May 24 '21 at 9:03
• @Hhan My question is the first one. I edited the title - thank you for pointing out. May 24 '21 at 9:05
• I am not fully sure it is what you want, but the plaintext encoding algorithm and power basis of Helib seems to be relevant. You can find a succinct description in eprint.iacr.org/2020/1481
– Hhan
May 24 '21 at 9:27

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).

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.

• Actually this was the exact concern I had in my mind. If I understood correctly, working over $\mathbb{C}$ and perform rounding & taking mod $q$ would give the correct result? I just wonder if the error is small enough so that the process always give a correct result. May 25 '21 at 5:08
• @SeewooLee As explained briefly in [DM15], the magnitude of the FFT error is expected to be $S\cdot \epsilon$, where $S = ||a \cdot a'||$ (prod. before reduction mod q) and $\epsilon$ is the error relative to floating-point arithmetic (thus, very small, like $2^{-30}$ or $2^{-50}$). If you want to obtain the exact product, then this error must be smaller than one half, since in this case the rounding erases it, i.e., if $||e|| < 1/2$, then $\lfloor a\cdot a' + e\rceil = a\cdot a'$. Maybe you can test it in practice with some FFT lib to check the size of $e$ for your choice of parameters... May 25 '21 at 6:19