Paper 2023/149

Demystifying Bootstrapping in Fully Homomorphic Encryption

Ahmad Al Badawi, Duality Technologies
Yuriy Polyakov, Duality Technologies

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.

Note: Added new FHEW/TFHE bootstrapping methods and updated experimental results in Table 1

Available format(s)
Publication info
Fully Homomorphic EncryptionBootstrappingBGVBFVCKKSDMFHEWCGGITFHEProgrammable Bootstrapping
Contact author(s)
ypolyakov @ openfhe org
2023-08-24: revised
2023-02-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ahmad Al Badawi and Yuriy Polyakov},
      title = {Demystifying Bootstrapping in Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/149},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.