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]
Related papers¶
- this paper follow up of Efficient Homomorphic Integer Computer from CKKS — follow-up listed for scheme "CKKS integer computer"
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