Part 7: TFHE Scheme #1 | Building Blocks of FHE

Among the various FHE schemes, the Fast Fully Homomorphic Encryption over the Torus (TFHE) scheme stands out for its remarkable efficiency and practical applicability. TFHE leverages the mathematical properties of the torus to perform fast and secure computations on encrypted data.

What Is Torus?

In mathematics, a torus is a surface of revolution generated by revolving a circle in three-dimensional space about an axis coplanar with the circle. More formally, it is a product of two circles, often denoted as $ S^1 \times S^1 $ or $\mathbb{R}/\mathbb{Z} = \mathbb{R} mod 1$.

$(\mathbb{T}, +, \cdot)$ is a $\mathbb{Z}$-module with operations:

• $ + : \mathbb{T} \times \mathbb{T} \rightarrow \mathbb{T} $,
• $ \cdot : \mathbb{Z} \times \mathbb{T} \rightarrow \mathbb{T} $.

Torus Polynomials

Torus polynomials are basically the set of polynomials with coefficients from the torus.

This set is denoted as $\mathbb{T}_n[x] = \mathbb{T}[x] mod (x^n + 1)$. Here $(\mathbb{T}_n[x], +, \cdot)$ is a $Z_n[x]$-module. Hence the operations within the polynomial structure are similar to the ones on the torus. So multiplication of two torus polynomials is not defined, but multiplication of a torus polynomial and an integer polynomial is defined.

LWE Over the Torus (TLWE)

Let‘s try to construct a learning-with-errors encryption over the torus.

Let $m \in \mathbb{T}$ be the message that we want to encrypt, $s \in {0, 1]^n$ the secret key, and $c = (a, b) \in \mathbb{T}^{n+1}$ our ciphertext pair where

• $a \in \mathbb{T}^n$,
• $ b = a \cdot s + \epsilon + m $. 

Here, $\epsilon \in \mathbb{T}$ is the error sampled from a Gaussian distribution.

RLWE Over The Torus (TRLWE)

Now, let’s move one step further and set up an RLWE system by following the same logic.

This time, our message $m$ is from $\mathbb{T}_n[x]$. Similarly, the secret key $s$ comes from the set of polynomials (modulo $x^n + 1$) with binary coefficients: ${0, 1}_n[x]$. Hence, our ciphertext pair will be $c = (a, b) \in \mathbb{T}_n[x]^2$ where

• $a \in \mathbb{T}_n[x]$,
• $ b = s \cdot a + \epsilon + m $.

Here $\epsilon \in \mathbb{T}_n[x]$ is a Gaussian error.

GSW Over the Torus (TGSW)

Before moving forward, let’s see one more scheme which we haven’t discussed so far.

GSW (Gentry-Sahai-Waters) encryption is another fully homomorphic encryption (FHE) scheme that enables the evaluation of arbitrary circuits on encrypted data. It is particularly known for its use in constructing efficient and practical FHE schemes.

GSW encryption represents ciphertexts as matrices. Each element of the matrix is an encryption of either a part of the message or zero. The plaintext message m is encoded into a matrix form. For simplicity, consider $m$ to be a binary value (0 or 1).

The ciphertext is constructed as a matrix $ C $ where each entry is an encryption of the message $ m $ or zero. The matrix $ C $ can be expressed as:

     $$C = A \cdot S + E + m \cdot G$$

where:

     - $ A $ is a random matrix.

     - $ S $ is the secret key matrix.

     - $ E $ is an error matrix with small entries.

     - $ G $ is a gadget matrix used to encode the message.

By leveraging these homomorphic operations, GSW encryption allows complex computations on encrypted data while preserving data privacy and security. The use of matrix representations and bootstrapping techniques ensures that noise levels remain manageable, allowing for practical and efficient fully homomorphic encryption.

Look Up Tables (LUTs)

Let's go through a basic toy example of using a Look Up Table (LUT) in TFHE to homomorphically evaluate a simple function. We'll use a small binary function to illustrate this concept.

Suppose we have a simple binary function $ f $ defined as follows:

$$ f(x_1, x_2) = x_1 \text{ AND } x_2 $$

This function takes two binary inputs and returns their logical AND.

To evaluate this function using a LUT, we need to precompute and store the results for all possible inputs. For two binary inputs $ x_1 $ and $ x_2 $, there are $ 2^2 = 4 $ possible input combinations. We create the following LUT:

In TFHE, we would encrypt the binary inputs $ x_1 $ and $ x_2 $ using TLWE encryption. Let's denote the encrypted values as $ \text{Enc}(x_1) $ and $ \text{Enc}(x_2) $.

To homomorphically evaluate $ f(x_1, x_2) $, we perform the following steps:

1. Encode the LUT in TRLWE: Store the LUT values in TRLWE ciphertexts. Each LUT value corresponds to the output of the function for a specific input combination.

2. Compute the Encrypted Index: Homomorphically compute the index of the LUT that corresponds to the encrypted inputs. This involves a series of homomorphic operations to determine the correct row in the LUT based on the values of $ \text{Enc}(x_1) $ and $ \text{Enc}(x_2) $.

3. Access the LUT: Use the homomorphically computed index to retrieve the corresponding LUT value without decrypting the inputs or the LUT values.

CMUX Operation

A CMux (Ciphertext Multiplexer) is an important component in the TFHE scheme. It is used to conditionally select between two encrypted values based on a control bit, all while keeping the data encrypted. This operation is fundamental for many homomorphic operations, including blind rotation and gate bootstrapping.

In the context of homomorphic encryption, a CMux performs the selection operation on encrypted data without decrypting it. The control bit that dictates the selection is also encrypted.

Given two encrypted values $ C_0 $ and $ C_1 $, and an encrypted control bit $ C_{\text{ctrl}} $, the CMux operation can be defined as follows:

$$ \text{CMux}(C_{\text{ctrl}}, C_0, C_1) = C_{\text{ctrl}} \cdot C_1 + (1 - C_{\text{ctrl}}) \cdot C_0 $$

Where:

- $ C_0 $: The ciphertext for the first input.

- $ C_1 $: The ciphertext for the second input.

- $ C_{\text{ctrl}} $: The ciphertext of the control bit (usually a GSW or TRGSW ciphertext).

The result is a ciphertext that encrypts $ C_1 $ if $ C_{\text{ctrl}} $ is 1, and $ C_0 $ if $ C_{\text{ctrl}} $ is 0, all in encrypted form.

Key Switching

Key switching is a crucial operation in TFHE that enables the transformation of a ciphertext encrypted under one secret key into an equivalent ciphertext encrypted under a different secret key. This mechanism is essential for facilitating computations across different encryption contexts without decrypting the data, preserving both security and flexibility.

Core Concept

Consider a ciphertext ccc encrypted under a secret key $\mathbf{s}$. Key switching involves producing a new ciphertext $c′$ such that:

$$\text{Decrypt}_{\mathbf{s}'}(c') = \text{Decrypt}_{\mathbf{s}}(c)$$

where $\mathbf{s}’$ is the target key. This transformation allows seamless compatibility across different keys in multi-party computation scenarios or when different components of a system use distinct encryption keys.

Procedure

1. Decomposition: The ciphertext ccc is decomposed into smaller components to facilitate efficient key switching. This is typically done by expressing the coefficients of $c$ in a base $B$, creating a set of smaller integers:
   $$ \{ c_1, c_2, \dots, c_k \} $$
   where $k$ depends on the size of the ciphertext and the chosen base.
2. Key Switching Matrix: A precomputed key switching matrix, denoted as $KS(\mathbf{s}, \mathbf{s}')$, is used to map the ciphertext components from $\mathbf{s}$ to $\mathbf{s}’$. This matrix contains encryptions of the original key $\mathbf{s}$ under the target key $\mathbf{s}’$.
3. Homomorphic Combination: The decomposed components $\{ c_i \}$ are combined with the key switching matrix using homomorphic operations to generate the new ciphertext $c′$. Each component contributes a partial result:
   $c' = \sum_{i=1}^k c_i \cdot KS(\mathbf{s}, \mathbf{s}')_i​$
   where $KS(\mathbf{s}, \mathbf{s}')_i$ represents the $i$-th row of the key switching matrix.
4. Output: The resulting ciphertext $c′$ is now valid under the target key $\mathbf{s}′$, maintaining the original plaintext while adapting to the new encryption context.

Conclusion

In this article, we discussed the foundational components of TFHE, focusing on the building blocks essential for understanding programmable bootstrapping. From exploring the mathematical properties of the torus to introducing key mechanisms like TLWE, TRLWE, TGSW, and key switching, we laid the groundwork for more advanced discussions. 

In the next article, we will build upon these concepts to unravel the essence of programmable bootstrapping. By leveraging the principles discussed here and introducing the concept of blind rotation, we aim to provide a comprehensive explanation of how programmable bootstrapping actually works.