Paper 2026/853

Faster Bootstrapping for Fully Homomorphic Encryption over Mixed-Radix Cyclotomic Ring

Abstract

Homomorphic matrix arithmetic is central to many data-intensive fully homomorphic encryption (FHE) applications, including privacy-preserving machine learning. Standard CKKS over power-of-two cyclotomic rings provides only a one-dimensional slot structure, forcing encrypted matrix operations to rely heavily on cyclic slot rotations and the associated key-switching overhead. Although the multivariate cyclotomic ring introduced by Jang et al. (AsiaCCS 2022) and later leveraged by Gentry--Lee (Crypto 2026) naturally supports matrix-structured computations, existing implementations still rely on Number-Theoretic Transforms (NTTs) based on Rader's algorithm for the non-power-of-two dimensions, making homomorphic arithmetic inefficient. Moreover, they lack an efficient bootstrapping algorithm. We instantiate CKKS over a mixed-radix cyclotomic ring whose order has \(2\) and \(3\) as prime factors, yielding a bivariate slot structure with independent row and column rotations. By realizing efficient NTT-based polynomial arithmetic over this ring and developing homomorphic radix-\(3\) FFT algorithms for the slot-to-coefficient (StC) and coefficient-to-slot (CtS) transformations in bootstrapping, we obtain the first practical end-to-end implementation of CKKS over this mixed-radix ring, thereby broadening the parameter space of CKKS beyond conventional power-of-two ring degrees. Based on this foundation, we further present an efficient bootstrapping algorithm for Gentry--Lee. Our mixed-radix decomposition factors the Discrete Fourier Transform and its inverse underlying StC and CtS into their radix-\(2\) and radix-\(3\) local counterparts. Exploiting the inherent batch structure of Gentry--Lee, we evaluate these components as batch plaintext--ciphertext matrix multiplications. This formulation replaces rotation-heavy linear transformations with matrix multiplications over cleartexts that can be accelerated by high-performance libraries such as BLAS and FLINT. Our proof-of-concept implementation achieves up to $5.31\times$ and $2.96\times$ speedups in amortized runtime for CtS and for full bootstrapping, respectively, over our optimized single bootstrapping, and is up to $1.87\times$ and $1.39\times$ faster than the construction of Crockett et al. (Crypto 2026).