Bootstrapping

Every homomorphic operation, especially multiplication, injects error into a ciphertext. This noise growth is inherent to lattice-based schemes like RLWE. Once the noise exceeds a critical threshold, decryption fails. Bootstrapping solves this by refreshing the ciphertext, reducing noise to a nominal level without decrypting the underlying data. Think of it as a cryptographic 'reset' button that trades computational cost for unlimited depth.

The core of bootstrapping is evaluating the scheme's own decryption algorithm homomorphically. The server holds an encrypted ciphertext c and an encrypted version of the secret key sk (provided as bootstrapping keys). It computes Decrypt(sk, c) entirely in the encrypted domain. The output is a new ciphertext encrypting the same plaintext but with a fresh noise budget. This circular security assumption is the foundational breakthrough of Gentry's blueprint.

In the TFHE scheme, bootstrapping is extended beyond noise reduction. Programmable Bootstrapping evaluates a univariate lookup table (LUT) simultaneously with the noise refresh. This allows the evaluation of arbitrary non-linear functions, such as activation functions (ReLU, sigmoid), in a single atomic operation. PBS is the critical enabler for efficient encrypted inference on deep neural networks, turning a noise management necessity into a functional computation step.

Bootstrapping is computationally intensive, often dominating the latency of FHE workloads. The choice of scheme dictates the trade-off:

• TFHE: Optimized for fast gate-by-gate bootstrapping (microseconds per gate), ideal for boolean circuits.
• CKKS/BGV: Supports amortized batch bootstrapping, refreshing thousands of packed ciphertext slots simultaneously. Latency is higher per operation, but throughput is massive for SIMD-style vector processing.
• Circuit Bootstrapping: A TFHE variant that produces a low-noise output suitable for subsequent operations, enabling composable function evaluation.

To perform bootstrapping, the server requires a public evaluation key called the bootstrapping key. This key is an encrypted version of the secret key, created by the data owner. While it enables noise refresh, it introduces a circular security assumption: the scheme remains secure even when the server possesses an encryption of the secret key under its own public key. This is a standard, widely accepted assumption in modern lattice-based cryptography, but it remains a distinct hardness property.

A Leveled FHE scheme can evaluate circuits up to a pre-determined multiplicative depth. Bootstrapping removes this depth constraint. By inserting a bootstrapping step after every few layers of computation, a leveled scheme becomes Fully Homomorphic Encryption (FHE), capable of evaluating arbitrary-depth circuits. This is the critical distinction: without bootstrapping, you must know the computation's complexity in advance; with it, you can run unbounded programs on encrypted data.