Skip to content

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