A question we are often asked, and one that our engineers also ask, is "What is bootstrapping?".
From a theoretical perspective, there is an easy answer: bootstrapping is applying the idea (due to Gentry) of homomorphically evaluating the decryption operation using an encryption of the secret key. But this explanation can be confusing and does not really explain bootstrapping in the context of the different FHE schemes currently available in various libraries.
To understand bootstrapping, we first need to understand two properties of a homomorphically encrypted ciphertext. Each ciphertext can have an associated "level" and a value of "noise". The noise value is associated with the ciphertext no matter what the underlying scheme is; whether it is BGV, BFV, CKKS or TFHE. The level is only associated with ciphertexts from the BGV, BFV and CKKS families. In most of these schemes, when a homomorphic multiplication is performed, one consumes a level. This means that the level value associated with the ciphertext is decreased by one and, in addition, we increase the noise.
After a certain number of operations - the exact number depending on the specific scheme - we can go no further. This is either because we have reached level zero (we have performed a given number of multiplications) or the noise has grown too big (for example, by doing a huge number of additions) or, more commonly, both.
It is at this point we bootstrap. This returns the level to a higher value, and, depending on the scheme, it may also reduce the noise. Bootstrapping is generally considered an expensive operation (even if improvements have already made it faster), so one usually tries to avoid it as much as possible.
To make matters slightly more confusing, one often sees different runtimes for the same implementation of the same scheme. Runtime can be thought of in four ways:
- The first, and most obvious way, is via the latency; how long do I have to wait until one bootstrap operation is carried out?
- Secondly, for BGV, BFV, CKKS, there is a notion of ciphertext packing. This notion can lead a developer to consider the amount of amortization due to packing,, i.e. how many plaintext slots can be bootstrapped per second? This gives a good measure of throughput, and it is basically equal to the number of slots supported divided by the latency (in seconds). This type of amortization comes from a purely mathematical optimization.
- The third way to measure performance is by exploiting the amortization one can obtain via instruction level parallelism, i.e. utilizing sliced implementation strategies, multiple threads or even a GPU. This type of amortization comes not from mathematics but from better implementation. This can also be expressed in terms of the number of slots bootstrapped per second.
- The fourth measure of performance (used in [1]) considers the product of the number of slots and the amount of multiplicative depth each bootstrapping operation provides, divided by the time to execute a single bootstrap operation. We will not consider this level of amortization further in this article.
However, in most applications, one is interested in low latency operations and not high throughput, i.e. we want to get one function evaluation quickly and not lots of evaluations of the same function slowly. Thus the key performance factor in many applications is latency.
To understand this in more detail, one must examine the effect of bootstrapping on levels and noise, as well as performance, in the context of the precise scheme used. And this is where confusion arises since bootstrapping behavior in one scheme may not intuitively carry over to the behavior in another scheme.
Now, let’s summarize what happens for the three main families of FHE schemes currently available in libraries:
BGV/BFV
In these schemes, bootstrapping increases the level associated with a ciphertext, and also reduces the noise. The input and output ciphertext from the bootstrap operation will encrypt the same underlying message (i.e. the clear message is not modified). A BGV/BFV computation looks like a sequence of additions and multiplication operations, where one tries to minimize the depth of the multiplication operations. The higher the depth, the more bootstrap operations are needed. Bootstrapping in BGV/BFV takes a long time, i.e. it has high latency, however, due to ciphertext packing, one can obtain reasonable amortized times. The table below provides further information.
CKKS
In CKKS, a plaintext already has noise associated with it, as each plaintext approximates a real number. Bootstrapping in this case does not reduce noise. It simply increases the level associated with a ciphertext. This means that the input and output ciphertexts will not encrypt the same underlying message (i.e. the underlying message is modified). They will, however, encrypt (different) approximations to the same real number. The “error” in the underlying real approximation is nevertheless increased by the bootstrapping, as it is for all operations. Thus, to evaluate a really deep circuit, one needs to take very large parameters. This means that one still needs to worry about error build up over a long sequence of operations. Generally speaking, CKKS bootstrapping has roughly the same latency as a BGV/BFV bootstrapping. See the table below for details.
TFHE
In TFHE, bootstrapping is a bit like BGV/BFV bootstrapping in that the noise is reduced, but since there is no notion of levels, we do not need to worry about this. However, there are two important differences. The first difference is that the latency is very small, allowing thousands of bootstrap operations to be performed per second, even more when we consider GPU acceleration as well. The second difference is that, during the bootstrap operation, one can evaluate a lookup table homomorphically for free, a procedure which is called Programmable Bootstrapping. For example, suppose a ciphertext encrypts a four-bit value, i.e. a value in [0,...,15]. Then, during bootstrapping, we can evaluate any function which maps four bits to four bits for free. This means that a TFHE computation becomes a sequence of additions, multiplication AND lookup table evaluations. So not only is bootstrapping orders of magnitude faster, but computations can be expressed in a richer language. This results in fewer necessary operations to evaluate a complex function overall, and no need to increase parameter sizes to deal with deep circuits (as in CKKS). Again, the table below helps to clarify
Summary
Bootstrapping allows a homomorphic computation to be carried on and on and on. It does this by modifying the level and noise associated with a ciphertext. How this happens, and the associated latency and throughput, depends on the specific scheme one is considering. To summarize the situation, we give the following table, taken from the papers we are aware of on the subject.
For the BGV times from [1], we utilized thin-bootstrapping timings, i.e. these are timings in which we assume that each plaintext slot contains an element of the base field/ring and not an extension field/ring. This is probably the variant which is most relevant in practical applications.
Note that for BGV, one could also consider the fourth measure of performance, i.e. the amortized cost of bootstrapping, over all possible slots AND the number of potential future multiplications which can be done for “free” (i.e. without another bootstrap). We do not consider that in the table, but one can think of this as multiplying the throughput by a factor of somewhere between 15 and 30 depending on the specific parameter set.
Note [2] presents a design for a hardware BGV accelerator which would give a latency of 40ms for a plaintext space of $Z/(127^3)Z$ and 64 slots. Similar orders of magnitude performance improvements (i.e. 3 orders of magnitude) are expected for the other schemes if dedicated hardware is used.
For the CKKS timing, we use the experiments from [3] which give a bootstrapping error of $2^{-25}$.
References
[1] Shai Halevi and Victor Shoup, Bootstrapping for HElib, Journal of Cryptology, Vol 34, Art 7, 2021.
[2] Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios Dimou, Ingrid Verbauwhede, Frederik Vercauteren, David W. Archer: BASALISC: Flexible Asynchronous Hardware Accelerator for Fully Homomorphic Encryption. IACR Cryptol. ePrint Arch. 2022: 657 (2022)
[3] Charanjit S. Jutla, Nathan Manohar: Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE. EUROCRYPT (1) 2022: 491-520
[4] Zama Team. Blog post “Announcing Concrete-core v1.0.0-gamma with GPU acceleration“, 2022. https://www.zama.ai/post/concrete-core-v1-0-gamma-with-gpu-acceleration
