Bootstrapping a ciphertext

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]noisyE[m]cleanE[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 bskbsk, which is an encryption under a key souts_{out} of the secret key sins_{in} used to encrypt the input ciphertext.

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

Generating a bootstrapping key

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 sins_{\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 sins_{\mathrm{in}}and a RLWE secret key to produce the RGSW ciphertexts of the bits composing sins_{\mathrm{in}}.

The generation of a bootstrapping key involves three parameters, a basis base_log , a number of levels level , and a polynomial size NN. 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 NNrelates to the discretization used for the bootstrapping, which in turn impacts the output precision. A larger value for NNincreases 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 parameterNNis 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> {
// settings
let base_log: usize = 5;
let level: usize = 3;
// secret keys
let sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);
let sk_in = LWESecretKey::new(&LWE128_630);
let sk_out = sk_rlwe.to_lwe_secret_key();
// bootstrapping key
let bsk = LWEBSK::new(&sk_in, &sk_rlwe, base_log, level);
// save the key to avoid regenerating it each time
bsk.save("my_bootstrapping_key.json");
// load it in memory
let loaded_bsk = LWEBSK::load("my_bootstrapping_key.json");
Ok(())
}

Bootstrapping a ciphertext

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> {
// encoders
let encoder_input = Encoder::new(-10., 10., 6, 1)?;
let encoder_output = Encoder::new(0., 101., 6, 0)?;
// secret keys
let sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);
let sk_in = LWESecretKey::new(&LWE128_630);
let sk_out = sk_rlwe.to_lwe_secret_key();
// bootstrapping key
let bsk = LWEBSK::new(&sk_in, &sk_rlwe, 5, 3);
// messages
let message: f64 = -5.;
// encode and encrypt
let c1 = LWE::encode_encrypt(&sk_in, message, &encoder_input)?;
// bootstrap
let c2 = c1.bootstrap(&bsk)?;
// decrypt
let output = c2.decrypt_decode(&sk_out)?;
println!("before bootstrap: {}, after bootstrap: {}", message, output);
Ok(())
}