Programmable bootstrapping is a powerful technique that enables simultaneously bootstrapping a ciphertext and homomorphically evaluating a function on it. Without programmable bootstrapping, evaluating complex non-linear functions would require evaluating deep arithmetic or boolean circuits, with as many bootstraps as there is noise accumulation. Here, the same function can be evaluated for the cost of a single bootstrap.
Just with plain bootstrapping, choosing the right parameters is paramount to get the right tradeoff between performances and precision.
Just as with plain bootstrapping, programmable bootstrapping requires at least one free bit of padding.
To apply a function on a ciphertext, use the bootstrap_with_function
method that takes as arguments:
a bootstrapping key.
the function to be evaluated, as a lambda Fn(f64) -> f64
, which can be any univariate function as long as it does not have side effects.
an output encoder that represents the range and precision of the resulting ciphertext, after the function has been applied to it.
Here is a code example to evaluate the square function:
A simple way to think of programmable bootstrapping is as a homomorphic table lookup, where the table represents a discretization of the function that needs to be evaluated on the ciphertext.
In TFHE, and thus Zama, we can bootstrap using polynomials modulo , and get as an intermediary step an encryption of a polynomial whose constant term is the input plaintext. Programming the bootstrapping operation then amounts to simply replacing this constant term by a table representing the discretized function being programmed. This table has to be provided with entries of the form with denotes the encoding function of the input and the encoding function of the output.
Operation
Type
Bootstrapped
Side effects
Reduces noise
Modifies padding
Potentially modifies encryption key
Potentially modifies security parameters