Paper 2026/2190

Stay in Your Lane: Fast Arithmetic over Large Finite Rings with CKKS

Abstract

Recent CKKS-based constructions support homomorphic arithmetic modulo powers of two and more general moduli. We explore a complementary tradeoff: using polynomial rings native to CKKS simplifies arithmetic and refreshing but restricts the message spaces. Building on Kim's interpretation of GBFV ciphertexts as CKKS ciphertexts, we use the decomposition $\mathbb{R}[X]/\langle X^N+1\rangle \cong(\mathbb{R}[X]/\langle X^n+1\rangle)^{N/n}$ into $N/n$ polynomial lanes, where $2\leq n\leq N$ is a power of two dividing the RLWE dimension $N$. Following GBFV, each lane represents a message in $\mathbb{Z}[X]/\langle X^n+1,t\rangle$, where $t$ is coprime to $X^n+1$ over $\mathbb{Q}$. These message spaces include $\mathbb{Z}_{\beta^n+1}$ for $t=X-\beta$, products of modular integer rings, specific 128-, 256-, 512-, and 1024-bit prime fields, and extension fields such as $\mathbb{F}_{5^{16}}$, $\mathbb{F}_{17^4}$, and $\mathbb{F}_{37^{32}}$. Unlike the triangle encoding of Gao and Zheng's construction (GZ), our lanes occur at intermediate stages of conventional CoeffToSlot and SlotToCoeff transformations, avoiding additional encoding-specific linear maps. We thus "stay in our lane" by performing arithmetic and refreshing within CKKS-native polynomial rings. Our arithmetic bootstrapping restores ciphertext levels, bounds polynomial representatives, and reduces approximation error. At $N=2^{16}$, it takes less than 4.5 seconds in every tested configuration, with little variation across $t$ and $n$. Comparing our arithmetic modulo $2^n+1$ with GZ's arithmetic modulo $2^n$, same-machine, same-library experiments show a $2.2\times$–$3.8\times$ speedup for $2^3\leq n\leq 2^6$. Our bootstrapping time remains nearly constant as $n$ grows, whereas GZ's dense encoding-specific transformations increase its cost and, at larger $n$, exceed available memory, preventing direct comparisons. At $n=2^{14}$, extrapolating GZ's published timings suggests a $26\times$ speedup.