In most of the RLWE based cryptosystems, the parameter $n$, which defines the cyclotomic polynomial $\Phi_{n}(X)$, is chosen to be a power of $2$.
Apart from other benefits such as ease of writing proofs and simplicity, are there any significant computational benefits?

  • 2
    $\begingroup$ The obvious advantage is the polynomial modular reduction, which is very easy for the modulus $x^n+1$. But I think that the main reason is that the FFT is more efficient when performed on the ring $R/qR$ where $R := \mathbb{Z}[x] / \langle x^n+1\rangle$ for suitable prime $q$ and $n$ being power of two. Notice that to perform homomorphic multiplication, we usually have to multiply polynomials in $R/qR$ and the FFT is used to speed up those multiplications. Hopefully, someone will show up to give a detailed answer. $\endgroup$ – Hilder Vitor Lima Pereira May 14 '19 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.