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