Paper 2026/2190

Stay in Your Lane: Scalable Large-Integer Arithmetic in CKKS

Abstract

Recent work has shown that the approximate homomorphic encryption scheme CKKS can perform exact modular arithmetic with large moduli. This enables high-precision integer computation: given bounds on the outputs of an arithmetic circuit, we can recover the exact integer results from the modular outputs using any sufficiently large modulus. The particular choice of modulus does not affect correctness. Long computations require periodic bootstrapping, which refreshes ciphertexts so that further operations remain possible. However, in Gao and Zheng's construction (Crypto '26) and its extensions by Wei et al. and Liu et al. (both ePrint '26), converting between the representations used for arithmetic and bootstrapping, which is required at every refresh, becomes increasingly expensive as the integers grow. We reduce this overhead by choosing message spaces that fit the representations already used inside standard CKKS bootstrapping. Building on GBFV (Geelen and Vercauteren; Eurocrypt '25) and its interpretation within CKKS (Kim; Asiacrypt '26), we organize encrypted data into independent polynomial “lanes” (namely, the factors of $(\mathbb{R}[X]/(X^n+1))^{N/n}$) that already appear as intermediate representations during bootstrapping (as intermediate stages of CoeffToSlot and SlotToCoeff). This avoids additional conversions specific to the message encoding. Supported message spaces include integers modulo $\beta^n+1$, where $n$ is a power of two and $\beta\geq2$ is a small integer, selected prime fields of up to $1\,024$ bits, and extension fields. For integer messages, we also give conversions in both directions between an arithmetic representation (for operations on whole integers) and a digit representation (for operations on their encrypted base-$\beta$ digits). We evaluate our construction and our port of Gao and Zheng in Lattigo on the same AWS Graviton5 hardware, using one thread at $N=2^{16}$ and targeting $128$-bit security. Our bootstrapping latency remains nearly constant for $8\leq n\leq2^{14}$ and stays below $8$ seconds across all tested message spaces, including $24\,577$-bit moduli ($n=4\,096$, $\beta=64$). For $8\leq n\leq1\,024$, this gives a speedup of $2.1\times$ to $6.8\times$ over the port, comparing arithmetic modulo $2^n+1$ with their arithmetic modulo $2^n$. These gains carry over to sustained computation: including bootstrapping to support arbitrary evaluation depth, we estimate amortized multiplication speedups of $3.2\times$ to $12.8\times$ over the port for $8\leq n\leq512$. As one concrete example, arithmetic bootstrapping takes $6.44$ seconds per ciphertext packing $16$ integers modulo $2^{4\,096}+1$. In sustained computation, the amortized cost is $0.22$ seconds per integer multiplication at over $4\,000$ bits of precision, including refreshing. Our arithmetic-to-digit conversion has per-call timings comparable to our implementation of Wei et al.'s conversion for $64\leq n\leq1\,024$ and $\beta=2$, and our analysis indicates better scaling for larger integers.