Programmable Bootstrapping

Traditional bootstrapping only refreshes the noise budget of a ciphertext. Programmable Bootstrapping performs this reset while simultaneously evaluating a lookup table (LUT) on the encrypted data. This means a single cryptographic operation both enables further computation and applies an arbitrary univariate function f(x) to the plaintext value, such as a ReLU activation or a sign function. This fusion eliminates the need to approximate functions with costly polynomial circuits before evaluating them.

The core mechanism relies on a blind rotation of a polynomial vector. The encrypted input value determines the rotation amount, effectively selecting a specific coefficient from a pre-computed polynomial that encodes the desired lookup table. This process is 'blind' because the server performing the rotation cannot see the actual rotation index. The result is an encrypted LWE sample containing the output of the function evaluated on the encrypted input.

Unlike other FHE schemes that require functions to be expressed as low-degree polynomials, Programmable Bootstrapping can evaluate any univariate function representable as a lookup table. This is critical for machine learning, enabling exact evaluation of non-linear activation functions like binary step, sign, or clipped ReLU without polynomial approximation errors. The function's precision is limited only by the size of the LUT encoded in the bootstrapping key.

In its simplest form, Programmable Bootstrapping evaluates a binary gate (e.g., NAND) on two encrypted bits, making TFHE a gate-bootstrapping scheme. This enables efficient evaluation of complex circuits. Extensions like multi-output PBS and circuit bootstrapping further optimize the evaluation of larger functions or convert between ciphertext formats (LWE to GSW), enabling composable operations within the TFHE ecosystem.

While CKKS relies on rescaling and polynomial approximation for non-linear functions, TFHE's Programmable Bootstrapping provides exact evaluation. This is a fundamental architectural trade-off:

• TFHE: Exact function evaluation on integers/bits, ideal for decision trees and discrete logic.
• CKKS: Approximate arithmetic on real numbers, ideal for high-throughput linear algebra in deep neural networks. The choice depends on the precision and type of computation required.

The unique properties of Programmable Bootstrapping enable hybrid FHE frameworks like CHIMERA. These architectures combine the strengths of multiple schemes:

• Use CKKS for fast, approximate linear layers of a neural network.
• Convert ciphertexts to TFHE using a specialized bootstrapping operation.
• Apply exact non-linear activations via Programmable Bootstrapping.
• Convert back to CKKS for subsequent layers. This approach achieves both high throughput and exact non-linearity.

PBS enables the evaluation of standard neural network activation functions directly on encrypted data. By encoding a lookup table (LUT) for functions like ReLU, Sigmoid, or Swish into the bootstrapping test vector, the operation simultaneously refreshes the ciphertext noise and applies the non-linearity.

• ReLU: Evaluated as a precise step function during the blind rotation.
• Sigmoid/Tanh: Approximated with high precision using polynomial or LUT encodings.
• Efficiency: A single PBS replaces a costly high-degree polynomial approximation, reducing multiplicative depth.

At its core, PBS is a programmable blind rotation that evaluates a function encoded as a Lookup Table. The ciphertext encrypting an integer x is rotated by x positions against a test vector encoding f(x), extracting the result.

• Arbitrary Functions: Any univariate function that fits within the LUT size can be evaluated.
• Precision: The LUT size determines the input domain precision (e.g., 10-bit inputs require a 1024-entry LUT).
• Composability: Multiple PBS operations can be chained to evaluate multi-variate functions via tree-based compositions.

PBS enables efficient integer arithmetic operations beyond simple addition and multiplication. By encoding arithmetic functions into LUTs, operations like division, modulo, and comparison are evaluated in a single step.

• Comparators: x > y is evaluated by encoding the comparison result into a LUT.
• Non-linear layers: Quantized neural network layers that require integer truncation or rounding use PBS to handle the discretization.
• Bitwise operations: AND, OR, XOR gates are natively supported in TFHE, with PBS enabling higher-level word operations.

Decision tree inference is natively supported by PBS. Each internal node's threshold comparison is a univariate function of the feature value, encoded as a LUT. The tree is traversed by composing these PBS-evaluated comparisons.

• Node evaluation: Each decision node is a single PBS operation.
• Privacy: The feature values and the decision path remain encrypted throughout the inference.
• Efficiency: Tree depth directly determines the number of PBS operations, making shallow trees or ensembles like random forests practical for FHE.

PBS enables private information retrieval patterns where a key is encrypted and the corresponding value is extracted from a table without revealing the key. This is a direct application of the LUT evaluation primitive.

• Private Search: An encrypted query index retrieves a database entry in a single PBS.
• Oblivious RAM Primitives: PBS serves as a building block for more complex oblivious data structures.
• Use Case: Private biometric matching where an encrypted template retrieves an associated identity or score.

PBS naturally aligns with quantized neural networks (QNNs). The LUT-based function evaluation maps directly to the quantization tables used in low-precision inference, making PBS the ideal FHE operator for deploying compressed models.

• Quantized ReLU: A simple step function that is trivially encoded in a LUT.
• Weighted Sums: Performed using standard homomorphic additions and multiplications before a PBS applies the activation and requantization.
• End-to-End: Frameworks like Concrete-ML automate the conversion of trained QNNs into PBS-based circuits.