Part 8: TFHE Scheme #2 | Building Blocks of FHE

Programmable bootstrapping is the centerpiece of the TFHE scheme, addressing the problem of noise accumulation while embedding computations directly into the noise-reduction process. This article explores the technical foundations and mechanics of programmable bootstrapping, covering key switching, blind rotation, and function evaluation via LUTs in rigorous detail.

Motivation for Programmable Bootstrapping

In Fully Homomorphic Encryption (FHE), every homomorphic operation adds noise to the ciphertext. If the noise exceeds a certain threshold, decryption fails, rendering the ciphertext unusable. Traditional bootstrapping resets the noise level by homomorphically evaluating the decryption function, effectively refreshing the ciphertext.

TFHE extends this concept further by allowing arbitrary functions to be computed homomorphically during bootstrapping. This approach reduces computational overhead, improves efficiency, and opens the door to practical applications such as encrypted logical circuits, machine learning inference, and privacy-preserving queries.

Ciphertext Types in TFHE

TFHE employs several ciphertext types, each designed for specific roles in the computation pipeline:

TLWE (Torus Learning With Errors):
TLWE ciphertexts encrypt a scalar value $m \in \mathbb{T}$ (the torus is represented as $\mathbb{T} = \mathbb{R}/\mathbb{Z}$). Encryption under a secret key $\vec{s} \in {0, 1}^n$ is defined as:

$$c = (a, b) \in \mathbb{T}^n \times \mathbb{T}$$

where $b = \langle a, \vec{s} \rangle + m + e$, and $e$ is a small Gaussian noise term sampled from $\mathcal{D}_{\mathbb{T}, \sigma}$.

GLWE (Generalized Learning With Errors):
GLWE extends TLWE to encrypt polynomials $M(X) \in \mathbb{T}[X]/(X^N + 1)$, where $N$ is the degree of the polynomial. A GLWE ciphertext under a polynomial secret key $\vec{S}$ is:

$$C = (\vec{A}, B) \in \mathbb{T}[X]^{k+1}$$

where $B = \langle \vec{A}, \vec{S} \rangle + M + E$, with $\vec{A} \in \mathbb{T}[X]^k$ and $E$ as polynomial noise.

GSW (Gentry-Sahai-Waters):
A GSW ciphertext represents an encrypted bit $b \in {0, 1}$ as a matrix of GLWE ciphertexts. This representation enables conditional operations, such as multiplexers (CMux), which are critical in programmable bootstrapping.

Each type serves a distinct purpose, allowing TFHE to balance computational efficiency and flexibility.

Key Switching

Key switching is a crucial operation that enables ciphertexts encrypted under one secret key to be transformed into ciphertexts encrypted under a different secret key. This is essential in programmable bootstrapping to align ciphertexts with the keys used by other operations, such as LUT evaluation.

Mathematical Representation

Given a TLWE ciphertext $c = (a, b)$ under a secret key $\vec{s}$, the goal is to produce a new ciphertext $c' = (a', b')$ under a new secret key $\vec{s}'$ such that:

$$b' = b - \langle a, \vec{s} \rangle + \langle a', \vec{s}' \rangle$$

Key Switching Procedure

Decomposition of Coefficients:
Decompose each coefficient of $a$ in base $B$:

$$a_i = \sum_{j=0}^{l-1} a_{i,j} B^j$$

where $l = \lceil \log_B(q) \rceil$ is the number of decomposition levels, and $q$ is the modulus.

Precomputed Key Switching Key (KSK):
The KSK is a table of GLWE ciphertexts encoding the products of the old key components with powers of $B$, encrypted under the new key:

$$\text{KSK}[i][j] = \text{GLWE}(\vec{s}[i] \cdot B^j; \vec{s}')$$

Homomorphic Combination:
Compute the new ciphertext as:

$$b' = b - \sum_{i=0}^{n-1} \sum_{j=0}^{l-1} a_{i,j} \cdot \text{KSK}[i][j]$$

The resulting ciphertext $c' = (a', b')$ is now compatible with the new secret key $\vec{s}'$.

Blind Rotation

Blind rotation is the key mechanism in programmable bootstrapping, enabling encrypted functions to be evaluated through conditional rotations of ciphertexts.

Mathematical Definition

Given a GLWE ciphertext $C = (\vec{A}, B)$ encrypting a polynomial $M(X)$ and a rotation factor $\pi$, the rotated ciphertext $C_\text{rot}$ is:

$$C_\text{rot} = (\vec{A} \cdot X^\pi, B \cdot X^\pi)$$

Here, $X^\pi$ represents the rotation polynomial, where $\pi$ can depend on the input or secret key.

Steps of Blind Rotation

Initialize Rotation:
Multiply each component of the GLWE ciphertext by $X^\pi$.

Iterative Rotation Using CMux:
CMux operations conditionally apply additional rotations based on the bits of a secret key $\vec{s}$. A CMux operation takes three inputs:

1. Two GLWE ciphertexts representing options $d_0$ and $d_1$.

2. A GSW ciphertext encrypting the selector bit $b$.

The output is:

$$d_b = b \cdot (d_1 - d_0) + d_0$$

Final Result:
After processing all key bits, the resulting ciphertext encodes the rotated polynomial $M(X \cdot X^{-\pi})$, aligned for LUT evaluation.

Look-Up Tables (LUTs) and Function Evaluation

Look-Up Tables (LUTs) are central to programmable bootstrapping, enabling the evaluation of arbitrary functions on encrypted inputs. The LUT is represented as a TRLWE ciphertext encoding precomputed function values.

Example: Binary AND Gate

To evaluate a binary AND function $f(a, b) = a \wedge b$, the LUT is defined as:

$$\text{LUT} = [0, 0, 0, 1]$$

where the indices correspond to input combinations $(a, b) \in \{(0, 0), (0, 1), (1, 0), (1, 1)\}$.

Evaluation Steps

1. Encode LUT in TRLWE Ciphertext:
   Each LUT entry is stored as an encrypted polynomial.
2. Compute Encrypted Index:
   Homomorphically compute the index corresponding to the encrypted inputs.
3. Retrieve Function Output:
   Access the LUT entry using blind rotation, outputting a ciphertext that encrypts $f(a, b)$.

Programmable Bootstrapping: The Full Pipeline

The programmable bootstrapping process integrates all the steps above into a seamless pipeline:

1. Input Encryption: Encrypt the input polynomial $M(X)$ using GLWE.
2. Key Switching: Transform the ciphertext to align with the key used in the LUT.
3. Blind Rotation: Rotate the ciphertext conditionally based on the secret key.
4. Function Evaluation: Use the rotated ciphertext to retrieve the appropriate LUT entry.
5. Noise Reduction: Refresh the ciphertext, ensuring it remains decryptable.

The final output is a ciphertext encrypting the result of the function $f(M)$ with reduced noise.

Conclusion

Programmable bootstrapping in TFHE is a groundbreaking innovation in FHE, enabling noise reduction and computation in a single operation. By leveraging operations like key switching, blind rotation, and LUT-based function evaluation, TFHE achieves unmatched efficiency and versatility for privacy-preserving computations.