Programmable Bootstrapping

PBS uniquely combines two critical operations into a single step. It resets the ciphertext noise budget to a nominal level, enabling unlimited computation depth, while concurrently evaluating an arbitrary univariate function f(x). This function is encoded as a lookup table (LUT) in the bootstrapping key, transforming the ciphertext from an encryption of m to an encryption of f(m) without ever decrypting.

Standard leveled HE schemes struggle with non-polynomial operations, requiring costly high-degree polynomial approximations. PBS solves this by evaluating the exact function via a lookup table.

• Exact ReLU: Evaluates max(0, x) precisely, avoiding approximation errors.
• Sign Function: Directly computes the sign of an encrypted value.
• Arbitrary Activation: Any univariate function like sigmoid or tanh can be evaluated with the same cost as a simple bootstrap.

The 'programmable' aspect is achieved by encoding the desired function into a test vector within the bootstrapping key. During bootstrapping, the ciphertext's phase is used to index this vector.

• Blind Rotation: A homomorphic operation that cyclically shifts the test vector based on the encrypted message.
• Extraction: The correct LUT entry is extracted as a new, refreshed ciphertext. This mechanism effectively performs a blind, univariate table lookup.

PBS is the fundamental building block for constructing deep encrypted neural networks. Because each PBS operation outputs a refreshed ciphertext with low noise, the output can be immediately used in subsequent operations.

• Unlimited Depth: Enables the evaluation of circuits of arbitrary multiplicative depth.
• Chaining Operations: A linear layer (additions/multiplications) can be followed by a PBS-based activation, and this pattern can be repeated indefinitely, making it ideal for deep learning inference.

It's crucial to distinguish standard TFHE bootstrapping from PBS.

• Standard Gate Bootstrapping: Refreshes noise and evaluates a NAND gate to enable binary circuit evaluation.
• Programmable Bootstrapping: Refreshes noise and evaluates a full univariate function over a larger message space (e.g., 8-bit integers), not just a binary gate. PBS is a generalization that operates on multi-bit messages, making it suitable for arithmetic computations in neural networks.

While early PBS implementations operated on single bits, modern schemes like TFHE-rs and Concrete support multi-bit PBS. This allows a single bootstrapping operation to process several bits of precision simultaneously.

• Throughput: Significantly increases the amortized throughput of encrypted computation.
• Trade-off: Multi-bit PBS increases the bootstrapping key size and computational cost per operation but reduces the total number of operations required for a given circuit, often resulting in a net latency reduction.

Two competing strategies for non-linear evaluation in FHE:

• Polynomial Approximation: Fits a low-degree polynomial to the target function. Works in leveled schemes like CKKS but introduces approximation error and struggles with sharp transitions
• LUT via Programmable Bootstrapping: Evaluates the exact function at every possible input value. No approximation error, handles discontinuities natively, but requires bootstrapping overhead Programmable bootstrapping is preferred when precision is paramount, such as in medical diagnostics or financial compliance models.