Skip to content

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

Authors: Hyeongmin Choe; Robin Köstler; Tim Seuré
Year: 2026

type: technique collection: schemes status: auto

Links: ePrint 2026/2190

Summary

Auto-extracted summary (unreviewed)

The paper builds exact homomorphic arithmetic over large finite rings inside CKKS by splitting the native ring R[X]/(X^N+1) into N/n polynomial 'lanes' R[X]/(X^n+1), each carrying a GBFV-style message in Z[X]/(X^n+1, t); this yields message spaces such as Z_{beta^n+1}, 128- to 1024-bit prime fields and extension fields, and the lanes arise at intermediate stages of ordinary CoeffToSlot/SlotToCoeff, so no encoding-specific linear maps are needed. An arithmetic bootstrapping that restores levels, bounds representatives and reduces error runs in under 4.5 s at N=2^16 in every tested configuration, is 2.2-3.8x faster than the GZ construction in same-machine Lattigo experiments for n in 2^3..2^6, and extrapolates to about 26x at n=2^14.

Abstract

Recent CKKS-based constructions support homomorphic arithmetic modulo powers of two [GZ26] and more general moduli [LMWW26, WMGZ26]. 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 [Kim25a], we use the decomposition R[X]/⟨XN + 1⟩∼= (R[X]/⟨Xn + 1⟩)N/n [HHC19] into N/n polynomial lanes, where n ∈J2, NK is a power of two dividing the RLWE dimension N. Following GBFV [GV25], each lane represents a message in Z[X]/⟨Xn + 1, t⟩, where t is coprime to Xn + 1 over Q. These message spaces include Zβn+1 for t = X −β, products of modular integer rings, specific 128-, 256-, 512-, and 1024-bit prime fields, and extension fields such as F516, F174, and F3732. Unlike GZ’s triangle encoding, 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 = 216, it takes less than 4.5 seconds in every tested configuration, with little variation across t and n. Comparing our arithmetic modulo 2n + 1 with GZ’s arithmetic modulo 2n, same-machine, same-library experiments show a 2.2×–3.8× speedup for n ∈ q 23, 26y . 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 = 214, extrapolating GZ’s published timings suggests a 26× speedup.
Source: pdf

Extracted details

Field Value Source Confidence
contribution lane decomposition of the CKKS ring enabling exact arithmetic over large finite rings and fields llm 0.85
contribution message spaces including Z_{beta^n+1}, products of modular rings, 128/256/512/1024-bit prime fields and extension fields llm 0.85
contribution arithmetic bootstrapping (Boot) and LazyFlatten refreshing within CKKS-native polynomial rings llm 0.85
contribution overflow and error-growth bounds for homomorphic operations llm 0.85
contribution Lattigo implementation and same-library comparison with GZ llm 0.85
schemes CKKS llm 0.85
schemes GBFV llm 0.85
libraries Lattigo llm 0.85
tasks exact modular arithmetic over large finite rings and fields llm 0.85
tasks CKKS arithmetic bootstrapping llm 0.85
hardware Apple M4 Pro (single thread, 24 GB memory) llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/tuneinsight/lattigo (URL found in the full text) regex 0.50
limitations message spaces are restricted to CKKS-native polynomial rings, giving less flexibility than GZ-style encodings llm 0.85
limitations comparison at large n combines different machines and extrapolated GZ timings llm 0.85
limitations GZ port exceeds available memory beyond n=2^6, preventing direct measurement llm 0.85
llm relevance low llm 0.85
key result arithmetic bootstrapping latency: 3.52-4.31 s (under 4.5 s) (N=2^16, t=X-2, n from 2^3 to 2^14, single thread Apple M4 Pro) llm 0.85
key result speed-up over GZ arithmetic bootstrapping: 2.2x-3.8x (same machine, same library (Lattigo), n in 2^3..2^6) llm 0.85
key result speed-up of lazy flattening over GZ A2A-I: 4.2x-16x (n in 2^3..2^7) llm 0.85
key result extrapolated speed-up over GZ: 26x (3.69 s vs 97.2 s) (n=2^14, using GZ published timings with square-root extrapolation) llm 0.85
key result amortized cost per multiplication: 1.99 s (n=2^3), 1.74 s (n=2^6) vs 6.62 s / 15.0 s for GZ port (including lazy flattening and periodic bootstrapping; 3.3x / 8.6x speed-up) llm 0.85
key result normalized error after bootstrapping: about 2^-35 vs 2^-23 for GZ port (respective parameters) llm 0.85

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 62 [p.1], BFV 4 [p.1], FHEW 2 [p.1]
  • library: Lattigo 12 [p.5], OpenFHE 4 [p.21], HElib 2 [p.27], Concrete (Zama) 2 [p.12]
  • hardware: Apple silicon 4 [p.5]
  • technique: Bootstrapping 60 [p.1], Key switching 24 [p.8], Rescaling 16 [p.9], Rotations 9 [p.7], Functional bootstrapping 4 [p.2], Relinearization 4 [p.9], RNS 4 [p.7]
  • assumption: RLWE 13 [p.1], Lattice-based 3 [p.27]
  • task: Language modeling / generation 7 [p.3]
  • topic: Benchmark 9 [p.20], Homomorphic encryption 8 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s12-1_eprint-2026-2190.pdf schemes 37 658.8 KB e21edd834499

Database key: stay-in-your-lane-fast-arithmetic-over-large-finite-rings-with-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set stay-in-your-lane-fast-arithmetic-over-large-finite-rings-with-ckks COLUMN VALUE