Skip to content

SHIP: A Shallow and Highly Parallelizable CKKS Bootstrapping Algorithm

Authors: J. H. Cheon; G. Hanrot; J. Kim; D. Stehl´e
Year: 2025
Venue: EUROCRYPT 2025

type: technique collection: catalogue, schemes, sok-references status: auto

Links: ePrint 2025/784

Visual lesson: SHIP bootstrapping · Scheme table row: SHIP bootstrapping

Summary

Auto-extracted summary (unreviewed)

SHIP is a new CKKS bootstrapping algorithm with very shallow multiplicative depth and high parallelizability, which lets the ring degree be reduced and enables the first bootstrapping of full-dimensional CKKS cleartext vectors at N=2^13 without switching to DM/CGGI. Implemented on top of HEaaN with several practical optimizations (level-saving trick, column-method blind rotation, base-B half-mux-rotate with hoisting), it bootstraps real-valued vectors in 215 ms on a 32-core CPU (2.5x lower latency than HEaaN on 48 cores) and binary vectors in 174 ms (2.2x lower than Bae et al., Eurocrypt'24).

Abstract

The CKKS fully homomorphic encryption scheme enables efficient homomorphic operations in terms of throughput, but its bootstrapping algorithm incurs a significant latency. In this work, we introduce SHIP, a novel bootstrapping algorithm for CKKS ciphertexts. SHIP enjoys a very shallow homomorphic multiplicative depth compared to state-of-the-art CKKS bootstrapping algorithms. Bootstrapping depth directly impacts the required Ring-LWE modulus, and hence the Ring- LWE degree. The massive depth saving allows us to report the first bootstrapping of CKKS ciphertexts for full-dimensional cleartext vectors in ring degree N “ 213, without resorting to an expensive scheme switching to DM/CGGI. SHIP also enjoys great parallelizability, with minimal communication between threads. The combined ring size reduction and high parallelizability lead to very low latency. In ring degree N “ 213, our experimental implementation runs in 215ms on a 32-core CPU for real-valued cleartext vectors. This is 2.5x lower than the smallest latency we could observe with the HEaaN library (using 48 cores). For binary cleartext vectors, the latency is lowered to 174ms, which is 2.2x lower than Bae et al [Eurocrypt’24] (with 32 cores).
Source: pdf

Extracted details

Field Value Source Confidence
contribution SHIP: a shallow-depth CKKS bootstrapping algorithm based on roots of unity encoding the secret key in the exponent llm 0.85
contribution First full-slot CKKS bootstrapping at ring degree N=2^13 without scheme switching to DM/CGGI llm 0.85
contribution Highly parallelizable design with minimal communication between threads, giving very low latency llm 0.85
contribution Practical optimizations: level-saving trick using the key-switching auxiliary modulus, column-method blind rotation hybridized with the mux method, base-B decomposition for half-mux-rotate combined with hoisting llm 0.85
schemes CKKS llm 0.85
libraries HEaaN llm 0.85
tasks CKKS bootstrapping llm 0.85
hardware 32-core CPU llm 0.85
security level 128-bit llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/malb/lattice-estimator (URL found in the full text) regex 0.50
code url https://github.com/zama-ai/tfhe-rs (URL found in the full text) regex 0.50
llm relevance low llm 0.85
key result bootstrapping latency: 215 ms (N=2^13, real-valued cleartext vectors, 32-core CPU) llm 0.85
key result latency reduction vs HEaaN: 2.5x (HEaaN using 48 cores) llm 0.85
key result bootstrapping latency: 174 ms (N=2^13, binary cleartext vectors, 32-core CPU) llm 0.85
key result latency reduction vs Bae et al. (Eurocrypt'24): 2.2x (binary cleartext vectors, 32 cores) llm 0.85

Scheme card: SHIP bootstrapping

Group 1. CKKS and its variants
Kind Variant
Hardness assumption RLWE
Plaintext type Approximate real/complex
SIMD packing Yes
Bootstrapping Yes, very shallow
Post-quantum Yes
Status Active SOTA
Fit for LLM inference Consumes few levels, but the SoK notes its keys are larger than classic bootstrapping.

System card: SHIP bootstrapping

Group 3. CKKS bootstrapping and operation advances
Family CKKS bootstrapping (blind-rotation inspired)
Arithmetic -
Interaction -
Model scale -
Status Active SOTA
Relation to the SoK Very shallow bootstrapping consuming few levels.
Note SoK notes its evaluation keys are larger than classical bootstrapping, so it needs refinement for LLMs.
Systems page SHIP bootstrapping

SoK reference [100]

J. H. Cheon, G. Hanrot, J. Kim, and D. Stehl´e, “Ship: A shallow and highly parallelizable ckks bootstrapping algorithm,” in Advances in Cryptology – EUROCRYPT 2025, S. Fehr and P.-A. Fouque, Eds. Cham: Springer Nature Switzerland, 2025, pp. 398–428.

Listed on the reference page of the site.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 98 [p.1], TFHE 17 [p.1], BGV 5 [p.1], BFV 3 [p.4], FHEW 3 [p.29]
  • library: HEaaN (library) 24 [p.1], HElib 3 [p.30], TFHE-rs 2 [p.30], Zama 1 [p.30]
  • hardware: FPGA 1 [p.3], AMD EPYC 1 [p.25], GPU 1 [p.3]
  • technique: Bootstrapping 143 [p.1], Rotations 66 [p.3], Rescaling 17 [p.10], RNS 11 [p.10], Key switching 6 [p.8], SIMD packing 4 [p.1], Relinearization 2 [p.11], Polynomial approximation 2 [p.2]
  • assumption: LWE 8 [p.1], RLWE 5 [p.1], Lattice-based 5 [p.4], 128-bit security 4 [p.4]
  • task: Language modeling / generation 4 [p.9]
  • topic: Homomorphic encryption 46 [p.1], Open source 2 [p.28]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/3-042_ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping.pdf catalogue 33 526.9 KB 3e8deccd8bd5
references/schemes/s08-0_ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping.pdf schemes 33 526.9 KB 3e8deccd8bd5 byte-identical to references/catalogue/3-042_ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping.pdf
references/sok-references/100_ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping.pdf sok-references 33 526.9 KB 3e8deccd8bd5 byte-identical to references/catalogue/3-042_ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping.pdf

Database key: ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping-algorithm · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set ship-a-shallow-and-highly-parallelizable-ckks-bootstrapping-algorithm COLUMN VALUE