Paper 2026/1847

Order-Four Symmetry in BGV Bootstrapping: Faster Digit Extraction for Large Primes

Abstract

Bootstrapping is the computational bottleneck of BGV/BFV fully homomorphic encryption, scaling particularly poorly with large plaintext primes. Its two dominant stages: digit extraction and linear transforms. Recent work has reduced the digit-extraction polynomial degree via null-polynomial lattices and bounded-support constructions, but both evaluate the reduced polynomial via generic Paterson--Stockmeyer at cost $O(\sqrt{d})$ . We present two algebraic optimizations that address both stages simultaneously. For digit extraction, we prove that choosing the auxiliary radix $A$ with $A^2\equiv -1\pmod{p}$ induces an order-four character filter, forcing the canonical digit-extraction polynomial to satisfy $P_A(AX)+AP_A(X)=AX$ and eliminating all monomials $X^k$ with $k\not\equiv 1,3\pmod{4}$. The resulting structured decomposition$P_A(X)=\tfrac{1}{2}X+X^3Q(X^4)$ reduces non-scalar multiplications from $O(\sqrt{d})$ to $O(\sqrt{d/r})$. For linear transforms, we provide first concrete instantiation of a Galois-structured mixed-radix butterfly decomposition for non-power-of-two cyclotomics, reducing the automorphism count from $O(\sqrt{D})$ to $O(\log D)$. On the standard NTT-friendly large-prime set ($p=65537$, $m=2^{16}$, $32768$ slots), our single-threaded \HElib{} implementation achieves a $1.85\times$ digit-extraction speedup ($20.06$s to $10.81$s) and a $1.27\times$ total thin-bootstrapping speedup ($42.3$s to $33.3$s) over the state-of-the-art Ma et al.\ baseline, the three stages the method does not touch moving by at most one per cent. All comparisons are made against the Ma et al.\ baselines, run in the identical pipeline at the same auxiliary radix; across nineteen encrypted parameter sets with $1297\le p\le 65537$, the digit-extraction speedup is $1.72$--$1.88\times$ on general cyclotomic rings ($37637\le m\le 65047$) and $1.84$--$2.13\times$ on the power-of-two ring $m=2^{16}$. Every set we recommend is quoted with concrete bit security.