Bootstrapping Bits with CKKS¶
Authors: Bae, Cheon, Kim, Stehlé
Year: 2024
Venue: EUROCRYPT 2024
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2024/767
Visual lesson: Bit-CKKS (bootstrapping bits with CKKS) · Scheme table row: Bit-CKKS (bootstrapping bits with CKKS)
Summary¶
Auto-extracted summary (unreviewed)
Proposes CKKS bootstrapping algorithms (BinBoot and GateBoot) specialized for ciphertexts whose slots encode bits in the most significant positions, which lowers the modulus consumed by bootstrapping and yields the first full-slot bootstrapping at ring degree 2^14 (about 1.4 s single-threaded in HEaaN). The resulting ciphertext format matches DM/CGGI, and combined with fast ring packing it gives a DM/CGGI bootstrapping that beats the state of the art when a few hundred bootstraps are batched.
Abstract¶
The Cheon–Kim–Kim–Song (CKKS) fully homomorphic encryption scheme is designed to efficiently perform computations on real numbers in an encrypted state. Recently, Drucker et al [J. Cryptol.] proposed an efficient strategy to use CKKS in a black-box manner to perform computations on binary data. In this work, we introduce several CKKS bootstrapping algorithms designed specifically for ciphertexts encoding binary data. Crucially, the new CKKS bootstrapping algorithms enable to bootstrap ciphertexts containing the binary data in the most significant bits. First, this allows to decrease the moduli used in bootstrapping, saving a larger share of the modulus budget for non-bootstrapping operations. In particular, we obtain full-slot bootstrapping in ring degree 214 for the first time. Second, the ciphertext format is compatible with the one used in the DM/CGGI fully homomorphic encryption schemes. Interestingly, we may combine our CKKS bootstrapping algorithms for bits with the fast ring packing technique from Bae et al [CRYPTO’23]. This leads to a new bootstrapping algorithm for DM/CGGI that outperforms the state-of-the-art approaches when the number of bootstraps to be performed simultaneously is in the low hundreds.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | BinBoot and GateBoot: CKKS bootstrapping for binary data placed in the MSBs | llm | 0.90 |
| contribution | reduced bootstrapping modulus budget, enabling full-slot bootstrapping at N = 2^14 for the first time | llm | 0.90 |
| contribution | ciphertext format compatible with DM/CGGI (FHEW/TFHE) ciphertexts | llm | 0.90 |
| contribution | new DM/CGGI bootstrapping via combination with fast ring packing, competitive for low hundreds of parallel bootstraps | llm | 0.90 |
| contribution | low-latency and high-throughput parameter sets and experiments in HEaaN | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| schemes | TFHE | llm | 0.90 |
| schemes | FHEW | llm | 0.90 |
| libraries | HEaaN | llm | 0.90 |
| tasks | homomorphic binary circuit evaluation | llm | 0.90 |
| tasks | FHE bootstrapping | llm | 0.90 |
| hardware | Intel Xeon Gold 6242 2.8 GHz, 503 GiB RAM, single-threaded | llm | 0.90 |
| security level | about 128-bit (lattice estimator) | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| limitations | implementation is not optimized; intended to illustrate BinBoot/GateBoot performance | llm | 0.90 |
| limitations | comparison with CGGI timings taken from other work on different hardware | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | BinBoot latency: 1.36 s (N = 2^14, full real slots (2^13), precision 9.6 bits, single thread) | llm | 0.90 |
| key result | GateBoot latency: 1.39 s (N = 2^14, full real slots (2^13), precision 7.7 bits, single thread) | llm | 0.90 |
| key result | speed-up over DMPS24 (HEaaN FGb) bootstrapping: 6.55x (BinBoot vs 9.1 s FGb full-slot bootstrap, same machine) | llm | 0.90 |
| key result | break-even vs CGGI gate bootstrapping: 214 gates in parallel (GateBoot 1.39 s vs 6.49 ms per CGGI gate bootstrap (LMSS23)) | llm | 0.90 |
Scheme card: Bit-CKKS (bootstrapping bits with CKKS)¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Bits |
| SIMD packing | Yes |
| Bootstrapping | Yes, amortized faster than TFHE for large batches |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Turns CKKS into a high-throughput boolean FHE. |
System card: Bit-CKKS / bootstrapping bits with CKKS¶
| Group | 2. CKKS core and variants |
| Family | CKKS used for binary/small-integer data |
| Arithmetic | Bits and small integers via CKKS |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Active SOTA |
| Relation to the SoK | Turns CKKS into a fast boolean or integer FHE engine. |
| Note | Faster amortized bit bootstrapping than TFHE/FHEW for large batches. Bridges approximate and exact worlds. |
| Systems page | Bit-CKKS / bootstrapping bits with CKKS |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 77 [p.1], TFHE 47 [p.1], BFV 7 [p.1], BGV 7 [p.1], FHEW 7 [p.27], NTRU 3 [p.28], Hybrid HE / transciphering 3 [p.27], Scheme switching 3 [p.2], RSA 2 [p.28]
- library: HEaaN (library) 9 [p.2], OpenFHE 3 [p.27], HElib 2 [p.8], Lattigo 2 [p.8], Concrete (Zama) 2 [p.29]
- hardware: Intel Xeon 2 [p.7], GPU 1 [p.2]
- technique: Bootstrapping 173 [p.1], SIMD packing 14 [p.1], Polynomial approximation 9 [p.3], Rescaling 8 [p.6], Key switching 5 [p.9], RNS 5 [p.3], Relinearization 4 [p.3], NTT 4 [p.25], Functional bootstrapping 3 [p.29], Programmable bootstrapping 2 [p.2]
- assumption: LWE 24 [p.1], RLWE 15 [p.1], Lattice-based 6 [p.18]
- topic: Homomorphic encryption 27 [p.1], Open source 3 [p.27]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-029_bootstrapping-bits-with-ckks.pdf |
catalogue | 36 | 840.4 KB | b6d5bae88a6e |
|
references/schemes/s11-0_bootstrapping-bits-with-ckks.pdf |
schemes | 36 | 840.4 KB | b6d5bae88a6e |
byte-identical to references/catalogue/2-029_bootstrapping-bits-with-ckks.pdf |
Database key: bootstrapping-bits-with-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set bootstrapping-bits-with-ckks COLUMN VALUE