Bootstrapping in Fully Homomorphic Encryption (FHE)

Bootstrapping is a term used very often in the context of Fully Homomorphic Encryption (FHE). Anyone who has read any introductory material on FHE already knows that bootstrapping is the most sophisticated and compute-intensive component of an FHE scheme. Very few, beyond cryptographers working in the field, understand what the bootstrapping operation really is and that there are various bootstrapping methods, each with its own tradeoffs. Our goals in this document are to demystify the concept of bootstrapping, correct misperceptions that seem to be common in the field and provide a high-level comparison of bootstrapping methods available in common FHE schemes, so that a reader of this document can make well-informed decisions about choosing when and how to deploy FHE implementations.

We start with a brief introduction to homomorphic encryption, highlighting key concepts and historical milestones.  Homomorphic encryption (HE) is a type of encryption that enables computations on encrypted data without having access to the secret key. Fully homomorphic encryption is its most general form that can be used to evaluate arbitrary programs/computations on encrypted data. The idea of an FHE capability was first described by Rivest, Adleman, and Dertouzos back in 1978 (note that the first two were co-authors of the famous RSA scheme introduced around that time). To describe homomorphic encryption, they used the term privacy homomorphisms and formulated the following problem: “it remains to be seen whether it is possible to have a privacy homomorphism with a large set of operations which is highly secure”.

This problem could not be solved for 30 years, until at the end of 2008 Craig Gentry, a Ph.D. student at Stanford then, proposed the first FHE scheme. This was a monumental breakthrough not just in cryptography, but also in theoretical computer science; and bootstrapping was its key ingredient.

To introduce bootstrapping, we will try to answer three basic questions: “what is it?,” “why do we need it?,” and “how does it work?”

What is bootstrapping?

A good starting point is to look at the definition of bootstrapping in the Oxford Dictionary: bootstrap is defined as “pulling yourself up by your (own) bootstraps”. When we say an HE scheme is bootstrappable, it means that it can homomorphically evaluate its own decryption procedure in addition to at least one extra operation. As shown in Fig. 1, evaluating the decryption procedure in the classical sense requires a ciphertext and secret key as input and ensures the plaintext as output. In FHE, however, we deal with a homomorphic evaluation of the decryption procedure, i.e., bootstrapping, which uses an encrypted secret key and a ciphertext to generate an “equivalent” ciphertext that we can further compute on. The encrypted secret key, also called a bootstrapping or refreshing key, is provided by the secret key holder as part of the public key material.

Why use bootstrapping in FHE? 

All common FHE schemes are based on noisy encryptions (the noise is what guarantees the security of fresh encryption) in which evaluating homomorphic operations increases the noise magnitude and lowers the quality, i.e., computational budget, of ciphertexts. The primary usage of bootstrapping is to convert an exhausted ciphertext into an “equivalent” refreshed ciphertext. Exhausted ciphertexts contain high noise and cannot be operated on further, whereas refreshed ciphertexts can support further homomorphic operations. A secondary purpose of bootstrapping is to evaluate a function on the encrypted message during the bootstrapping operation. In this case, the output ciphertext of bootstrapping encrypts a function of the plaintext message rather than the message itself, in addition to reducing the noise in the input ciphertext. This form of bootstrapping is known as functional or programmable bootstrapping.

How does bootstrapping in FHE work?

All common bootstrapping methods follow the same blueprint introduced by Craig Gentry, that is, homomorphic evaluation of their own decryption procedure. However, the bootstrapping mechanisms vary across FHE schemes. In our in-depth whitepaper, we describe the bootstrapping mechanisms in DM (FHEW) / CGGI (TFHE), CKKS, and BGV/BFV FHE schemes. We highlight the key differences between the methods, and evaluate their performance based on timing experiments using the OpenFHE library and results reported in peer-reviewed scientific literature. Based on this analysis, we provide some practical guidelines. Note that as of the time of writing this paper, OpenFHE includes bootstrapping for CKKS, DM, and CGGI schemes. Bootstrapping for BFV/BGV is currently under development and will be included in a future release of OpenFHE.

Experimental setup

We summarize our performance analysis of bootstrapping for CGGI, CKKS, and BGV schemes. More detailed analysis of the performance results is provided in the white paper. We chose CGGI over DM because the former is slightly faster than DM for the typical security setting of uniform ternary secret distribution. The complexity of BGV and BFV bootstrapping is very similar, so it is sufficient to consider only BGV here. We use the CGGI and CKKS implementations in OpenFHE to run our experiments. For BGV, we use reported results from. Security parameters are chosen to correspond to the 128-bit security level.

Recommendations and concluding remarks

Our goal was to explain various bootstrapping methods and provide some guidelines that can be used in practice. Our main results can be summarized as follows:

• CKKS bootstrapping has the best performance when the ciphertext contains a large number of slots (more than 100) and/or higher precision is sought (more than 3-8 bits).
• DM/CGGI bootstrapping is more efficient when the number of slots is small (up to 100) and the desired precision is low (up to 3-8 bits).
• DM/CGGI bootstrapping can be used to efficiently evaluate arbitrary functions (over small integers) using lookup tables, whereas CKKS can evaluate relatively smooth functions (over real numbers) that can be adequately approximated using polynomials, e.g., Chebyshev interpolation.
• BGV/BFV bootstrapping is somewhat faster than DM/CGGI (if we consider slot-amortized time), but slower than CKKS. However, BGV bootstrapping does not natively support arbitrary function evaluation.
• Hardware acceleration can be applied to all these bootstrapping methods, and the available literature suggests the expected speed-up should be similar for all these methods.

At a higher level, we can use the above insights to formulate recommendations about when each of these FHE schemes is most useful:

• CKKS is most efficient for applications working with real numbers, often represented as floating-point numbers in practice. Hence, CKKS is the best option for many practical machine learning problems, such as logistic regression training and convolutional neural network inference, and statistical computations.
• DM and CGGI (aka FHEW and TFHE) are the best choice for applications that require arbitrary function evaluation over small integers. A common example is the evaluation of Boolean circuits. Another example is machine learning inference for some models.
• BGV and BFV are often used for applications that work with large vectors of small integers. Common examples include private information retrieval and private set intersection, which are often used in secure database query applications.

Many applications may require both large problem sizes (where CKKS works well) and arbitrary function evaluation (where CGGI performs well), e.g., decision tree training. In this case, scheme switching from CKKS to CGGI and back may be beneficial. The OpenFHE team is currently adding this capability to the library and will make it available in 2023.

To learn more about bootstrapping in fully homomorphic encryption in-depth, read our white paper: Demystifying Bootstrapping in Fully Homomorphic Encryption.

Yuriy Polyakov and Ahmad Al Badawi