CKKS Bootstrapping in less than 10ms¶
Year: 2026
type: technique collection: schemes status: auto
Links: ePrint 2026/2119
Summary¶
Auto-extracted summary (unreviewed)
This paper gives a fully specified CKKS bootstrapping construction that builds on SHIP's decryption-in-the-exponent blind rotations, adding narrow blind-rotation tables, complex-slot packing that halves the blind-rotation key, coefficient packing with one-time key reconstruction, and NTT fusion that turns the dominant computation into batched sparse matrix operations on GPUs; it also supports low-depth functional bootstrapping. On an NVIDIA RTX PRO 6000 it bootstraps a single ciphertext in 8.2 ms and 4.6 ms amortized for a batch of 64, matching HEAAN's undocumented 6.97 ms result.
Abstract¶
Bootstrapping enables deep homomorphic computation in CKKS by replenishing multiplicative levels. It remains one of the scheme’s most expensive operations. HEAAN reports a bootstrapping latency of 6.97ms, substantially faster than other publicly documented alternatives. However, the algorithmic and implementation techniques underlying this result have not been disclosed, leaving it unclear how such performance is achieved. In this work, we present a fully specified CKKS bootstrapping construction that achieves performance comparable to that reported by HEAAN. Building on SHIP (presented in Eurocrypt 2025), we introduce several algorithmic innovations that reduce communication and computational overhead while enabling efficient parallel execution. Our implementation bootstraps a single complex-valued ciphertext in 8.2ms and achieves an amortized latency of 4.6ms per ciphertext for a batch of 64. These results demonstrate practical sub-10ms CKKS bootstrapping.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | narrow blind-rotation that removes redundant table-selector multiplications | llm | 0.85 |
| contribution | complex-slot packing halving the evaluation-ready blind-rotation key | llm | 0.85 |
| contribution | coefficient packing with one-time reconstruction to cut key-transmission cost | llm | 0.85 |
| contribution | fusion of blind rotations with NTT-domain permutations for batched GPU execution | llm | 0.85 |
| contribution | low-depth functional bootstrapping within the same framework | llm | 0.85 |
| contribution | CPU and GPU implementation with sub-10 ms bootstrapping | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| tasks | CKKS bootstrapping | llm | 0.85 |
| hardware | NVIDIA RTX PRO 6000 GPU | llm | 0.85 |
| hardware | CPU | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| limitations | asymptotic operation counts are worse than hybrid SHIP and PaCo because candidate enumeration is linear | llm | 0.85 |
| limitations | SHIP's implementation was not publicly available for direct comparison on the same platform | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | bootstrapping latency: 8.2 ms (single complex-valued ciphertext, RTX PRO 6000 GPU) | llm | 0.85 |
| key result | amortized bootstrapping latency: 4.6 ms per ciphertext (batch of 64, RTX PRO 6000 GPU) | llm | 0.85 |
| key result | reference comparison: HEAAN reports 6.97 ms (techniques undisclosed) (prior art) | llm | 0.85 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 50 [p.1], RSA 2 [p.30]
- library: OpenFHE 10 [p.23], Microsoft SEAL 3 [p.22]
- hardware: GPU 19 [p.2], AMD EPYC 2 [p.22], CUDA 2 [p.22]
- technique: Rotations 81 [p.2], Bootstrapping 48 [p.1], NTT 18 [p.3], Functional bootstrapping 10 [p.3], RNS 9 [p.4], Key switching 8 [p.3], GELU 6 [p.21], Sigmoid 6 [p.21], SIMD packing 6 [p.1], Minimax approximation 2 [p.21], Remez 2 [p.21], Matrix multiplication 2 [p.16], Non-interactive 2 [p.31]
- assumption: Lattice-based 4 [p.1], RLWE 3 [p.1], LWE 3 [p.1]
- topic: Homomorphic encryption 19 [p.1], Open source 2 [p.27]
Related papers¶
- this paper follow up of PaCo: Bootstrapping for CKKS via Partial CoeffToSlot — follow-up listed for scheme "PaCo bootstrapping"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s09-1_eprint-2026-2119.pdf |
schemes | 35 | 497.2 KB | ae1ca8576066 |
Database key: ckks-bootstrapping-in-less-than-10ms · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set ckks-bootstrapping-in-less-than-10ms COLUMN VALUE