Faster Polynomial Evaluations for SIMD FHEs and Application to BGV in HElib

The cost of homomorphic multiplications for existing FHEs to evaluate a degree-$D$ polynomial $f(x)$ at some point $x$ is very expensive. When $x$ is encoded in a plaintext slot having a power-of-two degree $d = 2^\ell$ and $D \leq d$, one can efficiently evaluate $f(x)$ with $O(\log d)$ multiplications using the heuristic algorithms of Okada et al. (ASIACRYPT 2023). However, neither $d = 2^\ell$ nor $D\leq d$ is satisfied for most practical FHE parameters, and the Paterson–Stockmeyer (P-S) method with $O(\sqrt{D})$ multiplications remains the state-of-the-art for $d \neq 2^\ell$ or $D>d$. In this paper, we first present a polynomial evaluation algorithm with $O(\log d)$ multiplications for any non-power-of-two $d$ and $D\leq d$, which achieves the same asymptotic complexity as that of Okada et al. Then, we gave a polynomial evaluation algorithm with $O(\sqrt{D/d})$ multiplications for plaintext modulus $p>2$ and $d < D\leq d\log p$, which beats the P-S method by a factor of $\sqrt{d}$ and essentially achieves logarithmic multiplication complexity when $D \leq d \cdot \min(\log^2 D, \log p)$. As a major application, we implement our algorithms in experiment to evaluate the digit extraction polynomials of the BGV bootstrapping with parameter $d$ ranging from $14$ to $45$ in HElib, and obtain a $1.22-2.16\times$ speedup over the recent work of Ma et al. (EUROCRYPT 2024).