Efficient Homomorphic Integer Computer from CKKS¶
Authors: Kim
Year: 2025
Venue: TCHES 2025
type: scheme collection: schemes status: auto
Links: ePrint 2025/66 · link
Visual lesson: CKKS integer computer · Scheme table row: CKKS integer computer
Summary¶
Auto-extracted summary (unreviewed)
Builds a homomorphic unsigned-integer computer on top of discrete CKKS by representing a 64-bit integer as 16 four-bit chunks and implementing addition, subtraction, multiplication, comparison and shifts via CKKS-style functional bootstrapping and modular reduction. A single-threaded Lattigo prototype achieves an amortized 8.85 ms per slot for 64-bit multiplication, about 2870x faster than TFHE-rs in throughput (110x-157x for other operations), although per-ciphertext latency (e.g. 145 s for multiplication) is higher and only wins at >= 6-way parallelism.
Abstract¶
As Fully Homomorphic Encryption (FHE) enables computation over encrypted data, it is a natural question of how efficiently it handles standard integer computations like 64-bit arithmetic. It has long been believed that the CGGI/DM family or the BGV/BFV family are the best options, depending on the size of the parallelism. The discrete variant of CKKS, suggested by Drucker et al. [J.Cryptol.’24], provides an interesting alternative for integer computations. Notably, the modular reduction framework proposed by Kim and Noh [CiC’25] built on top of the CKKSstyle functional bootstrapping by Bae et al. [Asiacrypt’24] gives an efficient arithmetic modulo small integers. In this work, we propose a novel homomorphic computer for unsigned integer computations. We represent a large integer (e.g. 64-bit) as a vector of smaller chunks (e.g. 4-bit) and construct arithmetic operations relying on discrete CKKS. The proposed scheme supports many of the operations supported in TFHE-rs while outperforming it in terms of amortized running time. Notably, our homomorphic 64-bit multiplication takes 8.85ms per slot, which is more than three orders of magnitude faster than TFHE-rs.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Chunked representation of large unsigned integers over discrete CKKS | llm | 0.90 |
| contribution | SIMD homomorphic add/sub/mul/compare/shift relying on CKKS functional bootstrapping and modular reduction | llm | 0.90 |
| contribution | Proof-of-concept Lattigo implementation with 128-bit parameters | llm | 0.90 |
| contribution | Throughput 2-3 orders of magnitude above TFHE-rs on 64-bit operations | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| schemes | discrete CKKS | llm | 0.90 |
| libraries | Lattigo | llm | 0.90 |
| libraries | TFHE-rs | llm | 0.90 |
| tasks | 64-bit unsigned integer arithmetic | llm | 0.90 |
| tasks | homomorphic comparison and bit shift | llm | 0.90 |
| hardware | Apple M4 Max, 128 GB RAM (single thread) | llm | 0.90 |
| security level | ~128-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/tuneinsight/lattigo (URL found in the full text) | regex | 0.50 |
| limitations | High latency per operation (tens to hundreds of seconds); advantage is in throughput and requires sufficient parallelism | llm | 0.90 |
| limitations | Experiments limited to k <= 64 bits due to the constraint k <= l*2^l (extension requires larger chunk size) | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | amortized time, 64-bit multiplication: 8.85 ms per slot (vs 25400 ms TFHE-rs, 2870x) (log N=15, single thread, Apple M4 Max) | llm | 0.90 |
| key result | latency, 64-bit multiplication: 145 s (46 bootstrappings) (one packed ciphertext) | llm | 0.90 |
| key result | amortized time, 64-bit addition: 5.91 ms per slot (157x vs TFHE-rs) (single thread) | llm | 0.90 |
| key result | amortized time, 64-bit comparison: 6.23 ms per slot (110x vs TFHE-rs) (single thread) | llm | 0.90 |
| key result | break-even parallelism for latency: >= 6 parallel multiplications (vs TFHE-rs 64-bit multiplication) | llm | 0.90 |
Scheme card: CKKS integer computer¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Exact 64-bit integer arithmetic via discrete CKKS |
| SIMD packing | Yes |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Exact integer arithmetic for quantized-integer LLM layers within one scheme. |
| Follow-ups | Large finite rings with CKKS (2026/2190). |
| Follow-up papers in the archive | Stay in Your Lane: Fast Arithmetic over Large Finite Rings with CKKS |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 110 [p.1], TFHE 21 [p.1], BFV 18 [p.1], BGV 17 [p.1], Threshold HE 3 [p.5], FHEW 2 [p.24], Hybrid HE / transciphering 2 [p.22]
- library: TFHE-rs 10 [p.1], HElib 1 [p.24], Lattigo 1 [p.25], Concrete (Zama) 1 [p.4], Zama 1 [p.26]
- hardware: Apple silicon 1 [p.17]
- technique: Bootstrapping 105 [p.1], SIMD packing 10 [p.2], Lookup table 7 [p.2], Functional bootstrapping 5 [p.1], NTT 5 [p.2], Programmable bootstrapping 4 [p.1], Rescaling 2 [p.6], RNS 2 [p.22], Convolution 2 [p.3]
- assumption: RLWE 11 [p.1], LWE 5 [p.1], Module-LWE 2 [p.8], IND-CPA-D 2 [p.5]
- task: Language modeling / generation 2 [p.6]
- topic: Homomorphic encryption 33 [p.1], Open source 2 [p.25]
Related papers¶
- Stay in Your Lane: Fast Arithmetic over Large Finite Rings with CKKS follow up of this paper — follow-up listed for scheme "CKKS integer computer"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s12-0_efficient-homomorphic-integer-computer-from-ckks.pdf |
schemes | 26 | 629.1 KB | b82f6b6dbe22 |
Database key: efficient-homomorphic-integer-computer-from-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-homomorphic-integer-computer-from-ckks COLUMN VALUE