Skip to content

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