Skip to content

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]

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