4
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Hhan
    May 24 at 9:03
  • $\begingroup$ @Hhan My question is the first one. I edited the title - thank you for pointing out. $\endgroup$
    – Seewoo Lee
    May 24 at 9:05
  • $\begingroup$ 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 $\endgroup$
    – Hhan
    May 24 at 9:27
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Seewoo Lee
    May 25 at 5:08
  • 2
    $\begingroup$ @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... $\endgroup$ May 25 at 6:19
  • $\begingroup$ Thank you very much! $\endgroup$
    – Seewoo Lee
    May 26 at 0:01

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.