1

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?

AdveRSAry
  • 624
  • 3
  • 14
  • 2
    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. – Hilder Vitor Lima Pereira May 14 '19 at 10:16

0 Answers0