The issue with manipulating noisy ciphertexts in FHE is that each leveled operation will increase the noise, eventually overflowing on the significant data bits and rendering the resulting computing imprecise. To avoid this from happening and carry on computing forever, ciphertexts need to be "cleaned up" whenever the noise grows too big, using a special procedure called **bootstrapping**.

| |

Operation | $E[m]_{noisy} \rightarrow E[m]_{clean}$ |

Type | Bootstrapped |

Side effects | Reduces noise Modifies padding Potentially modifies encryption key Potentially modifies security parameters |

The original intuition behind bootstrapping (as introduced by Gentry) is that by homomorphically evaluating the decryption circuit, we can reset the noise in the ciphertext to a nominal level. This requires a public **bootstrapping key** $bsk$, which is an encryption under a key $s_{out}$ of the secret key $s_{in}$ used to encrypt the input ciphertext.

The bootstrapping operation thus works by taking as input a noisy ciphertext encrypted under some secret key $s_{\mathrm{in}}$ and a bootstrapping key $bsk$, producing a refreshed ciphertext (i.e., with a reduced amount of noise), encrypted under the secret key $s_{\mathrm{out}}$. A key-switch can then be performed to obtain a ciphertext encrypted under the original $s_{\mathrm{in}}$.

A bootstrapping key is a list of **RGSW ciphertexts**, which are themselves a collection of RLWE ciphertexts. Each RGSW ciphertext composing the bootstrapping key encrypts a bit of the secret key $s_{\mathrm{in}}$used to encrypt the input ciphertext. This explains why two keys are needed in the generation of a bootstrapping key: the input LWE secret key $s_{\mathrm{in}}$and a RLWE secret key to produce the RGSW ciphertexts of the bits composing $s_{\mathrm{in}}$.

The generation of a bootstrapping key involves three parameters, a basis `base_log`

, a number of levels `level`

, and a polynomial size $N$. The choice of these parameters is important as they affect the amount of noise and precision of the output ciphertext, as well as the computational cost of performing a bootstrap. They also determine the size of the bootstrapping key. For example, the parameter $N$relates to the discretization used for the bootstrapping, which in turn impacts the output precision. A larger value for $N$increases the output precision but it also increases the bootstrapping time. Thus, finding a set of parameters offering good performance trade-offs is essential.

For example, for an LWE ciphertext with dimension `n = 1024`

, setting the bootstrapping parameters to `N = 1024`

, `level=4`

and `base_log=6`

will guarantee 3 bits of precision in the output ciphertext, and 4 bits with a probability of 97%.

As a rule of thumb, it is good to try keeping a small value for `level`

. Generally, a good choice for parameter$N$is 1024 or any other higher power of two.

Bootstrapping keys can be several hundreds of megabytes large and take several minutes to generate using OpenSSL's secure pseudo-random number generator. During development, Rust's faster, but unsafe prng can be used by specifying the cargo flag "--features=unsafe" (never use this in production!).

Here is an example of how to generate a bootstrapping key:

use concrete::*;fn main() -> Result<(), CryptoAPIError> {// settingslet base_log: usize = 5;let level: usize = 3;// secret keyslet sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);let sk_in = LWESecretKey::new(&LWE128_630);let sk_out = sk_rlwe.to_lwe_secret_key();// bootstrapping keylet bsk = LWEBSK::new(&sk_in, &sk_rlwe, base_log, level);// save the key to avoid regenerating it each timebsk.save("my_bootstrapping_key.json");// load it in memorylet loaded_bsk = LWEBSK::load("my_bootstrapping_key.json");Ok(())}

Bootstrapping a ciphertext is done using the `bootstrap`

method, which takes the bootstrapping key as input. Although bootstrapping can free up padding, it will first need to consume one bit of padding.

There must be at least one available bit of padding in the input ciphertext to perform a bootstrapping operation on it.

use concrete::*;fn main() -> Result<(), CryptoAPIError> {// encoderslet encoder_input = Encoder::new(-10., 10., 6, 1)?;let encoder_output = Encoder::new(0., 101., 6, 0)?;// secret keyslet sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);let sk_in = LWESecretKey::new(&LWE128_630);let sk_out = sk_rlwe.to_lwe_secret_key();// bootstrapping keylet bsk = LWEBSK::new(&sk_in, &sk_rlwe, 5, 3);// messageslet message: f64 = -5.;// encode and encryptlet c1 = LWE::encode_encrypt(&sk_in, message, &encoder_input)?;// bootstraplet c2 = c1.bootstrap(&bsk)?;// decryptlet output = c2.decrypt_decode(&sk_out)?;println!("before bootstrap: {}, after bootstrap: {}", message, output);Ok(())}