Paper 2023/149
Demystifying Bootstrapping in Fully Homomorphic Encryption
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.
Note: Added new FHEW/TFHE bootstrapping methods and updated experimental results in Table 1
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Fully Homomorphic EncryptionBootstrappingBGVBFVCKKSDMFHEWCGGITFHEProgrammable Bootstrapping
- Contact author(s)
- ypolyakov @ openfhe org
- History
- 2023-08-24: revised
- 2023-02-08: received
- See all versions
- Short URL
- https://ia.cr/2023/149
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/149,
author = {Ahmad Al Badawi and Yuriy Polyakov},
title = {Demystifying Bootstrapping in Fully Homomorphic Encryption},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/149},
year = {2023},
url = {https://eprint.iacr.org/2023/149}
}