Skip to content

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]

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