Demystifying bootstrapping in fully homomorphic encryption¶
Authors: A. A. Badawi; Y. Polyakov
Year: 2023
type: survey collection: sok-references status: auto
Links: ePrint 2023/149
Summary¶
Auto-extracted summary (unreviewed)
This expository paper explains what FHE bootstrapping is, why it is needed and how it works, and compares the bootstrapping methods of CKKS, DM (FHEW), CGGI (TFHE), BGV and BFV using their implementations in OpenFHE and HElib at 128-bit security. The evaluation finds that CKKS bootstrapping gives the highest throughput and high precision for real-valued vectors, DM/CGGI give the lowest latency and support programmable bootstrapping via lookup tables, and BGV/BFV give higher throughput than DM/CGGI for small-integer vectors without programmable bootstrapping.
Abstract¶
Bootstrapping is a term used very often in the context of Fully Homomorphic Encryption (FHE). Anyone who is familiar with FHE knows that bootstrapping is the most sophisticated and compute-intensive component of an FHE scheme. However, very few non-FHE-experts understand what the bootstrapping operation really is and that there are various bootstrapping methods, each with its own tradeoffs. The goal of this paper is to provide a high-level introduction to common bootstrapping methods and evaluate their performance using the existing implementations in OpenFHE and HElib open-source libraries. Our performance evaluation suggests that the bootstrapping in the Cheon-Kim-Kim-Song (CKKS) scheme provides highest throughput and efficiently achieves large precision for vectors of real numbers, which are often used in machine learning applications. The Ducas-Micciancio (DM) and Chillotti-Gama-Georgieva-Izabachene (CGGI) schemes achieve the smallest latency (typically for small integers or small-precision fixed-point numbers) and provide a general capability for evaluating arbitrary functions (programmable bootstrapping) via lookup tables. The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes provide higher bootstrapping throughput than DM/CGGI for vectors of small integers or finite-field elements but do not support programmable bootstrapping. The target audience is anyone interested in FHE. We intend to keep this paper up-to-date to include new bootstrapping results as they become available.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | high-level introduction to FHE bootstrapping and correction of common misperceptions | llm | 0.80 |
| contribution | comparison of bootstrapping methods across CKKS, DM/FHEW, CGGI/TFHE, BGV and BFV | llm | 0.80 |
| contribution | performance evaluation using OpenFHE and HElib implementations | llm | 0.80 |
| schemes | CKKS | llm | 0.80 |
| schemes | FHEW | llm | 0.80 |
| schemes | TFHE | llm | 0.80 |
| schemes | BGV | llm | 0.80 |
| schemes | BFV | llm | 0.80 |
| libraries | OpenFHE | llm | 0.80 |
| libraries | HElib | llm | 0.80 |
| tasks | FHE bootstrapping benchmarking | llm | 0.80 |
| security level | 128-bit | llm | 0.80 |
| interaction | non-interactive FHE | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | highest bootstrapping throughput: CKKS (vectors of real numbers, large precision) | llm | 0.80 |
| key result | smallest bootstrapping latency: DM/CGGI (FHEW/TFHE) (small integers or low-precision fixed point, programmable bootstrapping) | llm | 0.80 |
| key result | throughput for small-integer vectors: BGV/BFV higher than DM/CGGI (no programmable bootstrapping) | llm | 0.80 |
SoK reference [22]¶
A. A. Badawi and Y. Polyakov, “Demystifying bootstrapping in fully homomorphic encryption,” Cryptology ePrint Archive, Report 2023/149, 2023. [Online]. Available: https://eprint.iacr.org/2023/149
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: TFHE 57 [p.1], CKKS 49 [p.1], BGV 24 [p.1], BFV 16 [p.1], FHEW 5 [p.2]
- library: OpenFHE 18 [p.1], HElib 4 [p.1], cuFHE / nuFHE 1 [p.7]
- model: Logistic regression 2 [p.5], Decision tree 1 [p.9]
- hardware: AVX-512 2 [p.7], GPU 1 [p.7]
- technique: Bootstrapping 118 [p.1], Programmable bootstrapping 9 [p.1], SIMD packing 5 [p.5], Lookup table 4 [p.1], Polynomial approximation 3 [p.5], Compiler 2 [p.7]
- topic: Homomorphic encryption 40 [p.1], Benchmark 8 [p.7], Open source 2 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/sok-references/022_demystifying-bootstrapping-in-fully-homomorphic-encryption.pdf |
sok-references | 11 | 264.6 KB | 3ed8f2ae0bcd |
Database key: demystifying-bootstrapping-in-fully-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set demystifying-bootstrapping-in-fully-homomorphic-encryption COLUMN VALUE