TFHE Deep Dive - Part I - Ciphertext types

> Part I: Ciphertext types
> Part II: Encodings and linear leveled operations
> Part III: Key switching and leveled multiplications
> Part IV: Programmable Bootstrapping

This blog post is part of a series of posts dedicated to the Fully Homomorphic Encryption scheme called TFHE (also known as CGGI, from the names of the authors Chillotti-Gama-Georgieva-Izabachène). Each post will allow you to go deeper into the understanding of the scheme. The subject is challenging, we know, but don’t worry, we will dive into it little by little.

Disclaimer: If you have watched the video TFHE Deep Dive, you might find some minor differences in this series of blog posts. That’s because here there is more content and a larger focus on examples. All the dots will connect in the end.

TFHE is a Fully Homomorphic Encryption (FHE) scheme. That means it is an encryption scheme that allows you to perform computations over encrypted data. To know more about FHE schemes in general, take a look at this blog post.

TFHE was initially proposed as an improvement of the scheme FHEW, and then it started developing in a broader direction. The security of the scheme is based on a hard lattice problem called Learning With Errors, or LWE in short, and its variants, such as Ring LWE (RLWE). In fact, the majority of FHE schemes used nowadays are LWE based and use noisy ciphertexts. TFHE is, however, distinguished from the others because it proposes a special bootstrapping which is very fast and able to evaluate a function at the same time as it reduces the noise.

A few blog posts will be necessary before we talk in detail about bootstrapping, so no rush for now in trying to understand how it works. Let’s start from “the beginning” by describing the ciphertexts used in TFHE.

Some notation

A few mathematical objects will be needed to understand this blog post series.

• $\mathcal{R} = \mathbb{Z}[X]/(X^N +1)$ the ring of integer polynomials modulo the cyclotomic polynomial $X^N + 1$, with $N$ power of 2. In practice, it contains integer polynomials up to degree $N-1$.
• $\mathcal{R}_q = (\mathbb{Z}/q\mathbb{Z})[X]/(X^N +1)$, i.e., the same ring of integers $\mathcal{R}$ as above, but this time the coefficients are modulo $q$. Observe that we often note $\mathbb{Z}/q\mathbb{Z}$ as $\mathbb{Z}_q$.
• Our modular reductions are centered around zero. As an example, when reducing modulo $8$, we use the congruence classes $\{ -4, -3, -2, -1, 0, 1, 2, 3 \}$.
• $\chi_{\mu, \sigma}$ is a Gaussian probability distribution with mean $\mu$ and standard deviation $\sigma$. If $\mu = 0$, we will simply note $\chi_\sigma$.
• We will use small letters for (modular) integers $(a, b, m, s, \ldots)$, we will use capital letters for polynomials $(A, B, M, S, \ldots)$.
• We will note the list of integer elements from $a\in \mathbb{Z}$ to $b\in \mathbb{Z}$ included, as $[a..b]$.
• We use the abbreviations MSB and LSB for Most Significant Bit and Least Significant Bit respectively.
• We denote with $\lfloor \cdot \rceil$ the rounding operation to the nearest integer value.

TFHE Ciphertexts

What is the first thing you talk about when you give a recipe? The ingredients, of course! In our case, the main ingredients are the ciphertexts.

In TFHE, we mainly use three types of ciphertexts: LWE, RLWE, and RGSW ciphertexts. Why we need three different types of ciphertexts, you might wonder. Long story short, the reason is that all of them have different properties which will be useful in the homomorphic operations that we will describe in the following blog posts. All of them have security that relies on the LWE problem or its variants. To know more about LWE security, please take a look at this blog post.

In this blog post we will give you more general definitions in order to help you understand the objects we manipulate.
These ciphertext are not only used in TFHE, but also in other LWE-based FHE schemes.

• GLWE (General LWE) - a generalization for both LWE and RLWE ciphertexts;
• GGSW (General GSW) - a generalization for RGSW ciphertexts;
• GLev - an intermediate ciphertext type that will be very useful to better understand GGSW ciphertexts and that we will largely use in the following blog posts.

Let’s start!

GLWE

If you’ve already heard about LWE based FHE schemes, you have also probably heard about LWE and RLWE ciphertexts.
In this section we will use a generalization that includes both of them, called General LWE, or GLWE in short.

To generate any kind of ciphertext, we first need a secret key. With  GLWE ciphertexts, the secret key is a list of $k$ random polynomials from $\mathcal{R}$:
$$ \vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k.$$

In particular, the coefficients of the $\mathcal{R}$ elements can be sampled from a uniform binary distribution, a uniform ternary distribution, a Gaussian distribution, or a uniform distribution.
Please note that for any of these types of secret keys, we can find parameters to archive a desired security level.
In this series of blog posts, as in the original TFHE description, we will assume that our secret keys are sampled from uniform binary distributions.

Now let’s see how to encrypt messages. Let $p$ and $q$ be two positive integers, such that $p\leq q$ and let’s define $\Delta = q/p$. In TFHE, $q$ and $p$ are often chosen to be powers of two: if they are not, a rounding at the moment of encoding of messages should be applied. We will call $q$ ciphertext modulus, $p$ plaintext modulus, and $\Delta$ scaling factor. Let’s consider a message $M \in \mathcal{R}_p$. A GLWE ciphertext encrypting the message $M$ under the secret key $\vec{S}$ is a tuple:

$$(A_0, \ldots, A_{k-1}, B) \in GLWE_{\vec{S}, \sigma}(\Delta M) \subseteq \mathcal{R}_q^{k+1}$$

where the elements $A_i$ for $i\in [0..k-1 ]$ are sampled uniformly random from $\mathcal{R}_q$, and $B = \sum_{i=0}^{k-1} A_i \cdot S_i + \Delta M + E \in \mathcal{R}_q$, and $E \in \mathcal{R}_q$ has coefficients sampled from a Gaussian distribution $\chi_{\sigma}$.
We often call $(A_0, \ldots, A_{k-1})$ the mask and $B$ the body. The polynomial $\Delta M$ is what we sometimes call an encoding of $M$. Observe that, to compute $\Delta M$, we lift the message $M$ as an element of $\mathcal{R}_q$. Also, every time we encrypt a message, we sample new randomness (mask and noise error), so every encryption (even of the same message) is different from the other. This is essential for security. The set of GLWE encryptions of the same encoding $\Delta M$, under the secret key $\vec{S}$, with Gaussian noise with standard deviation $\sigma$, will be noted $GLWE_{\vec{S}, \sigma}(\Delta M)$.

Now, if we have a ciphertext $(A_0, \ldots, A_{k-1}, B) \in GLWE_{\vec{S}, \sigma}(\Delta M) \subseteq \mathcal{R}_q^{k+1}$ encrypted under the secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$, then we can decrypt it by computing:

    1.    $B - \sum_{i=0}^{k-1} A_i \cdot S_i = \Delta M + E \in \mathcal{R}_q$,

    2.   $M = \lfloor (\Delta M + E)/\Delta \rceil$.

Observe that the message $M$ is in the MSB part of $\Delta M + E$ (thanks to the multiplication by $\Delta$) while $E$ is in the LSB part. If $|E|<\Delta/2$ (so if every coefficient $e_i$ of $E$ is $|e_i|<\Delta/2$), then the second step of the decryption returns $M$ as expected. If the error does not respect the condition, the decryption is incorrect. In the following image we represent the i-th coefficients of $\Delta M +  E$.

Toy example

To better understand GLWE ciphertexts, let’s make a toy example where we use parameters that are totally insecure, just to fix ideas.

Let’s choose $q=64$, $p=4$ so $\Delta = q/p = 16$. Let’s choose $N=4$ and $k =2$.

We sample the secret key with uniform binary distribution as $k$ polynomials of degree smaller than $N$:

$$
\vec{S} = (S_0, S_1) = (0 + 1\cdot X+1\cdot X^2 + 0\cdot X^3, 1 + 0\cdot X+1\cdot X^2 + 1\cdot X^3) \in \mathcal{R}^2.
$$
Let’s encrypt a message $M \in \mathcal{R}_p$, which is a polynomial of degree smaller than $N$ with coefficients in $\{ -2, -1, 0, 1 \}$, say:
$$
M = - 2 + 1\cdot X+ 0\cdot X^2 - 1\cdot X^3.
$$
In order to encrypt the message, we need to sample a uniformly random mask with coefficients in $\{ -32, -31, \ldots,$ $ -1, 0, 1, 2, \ldots, 30, 31 \}$:
$$
\vec{A} = (A_0, A_1) = (17 -2\cdot X-24\cdot X^2 + 9\cdot X^3, -14 + 0\cdot X-1\cdot X^2 + 21\cdot X^3) \in \mathcal{R}_q^2
$$
and a discrete Gaussian Error (small coefficients):
$$
E = -1 + 1\cdot X+0\cdot X^2 + 1\cdot X^3 \in \mathcal{R}_q.
$$
To encrypt, we need to compute the body as :
$$
B = A_0 \cdot S_0 + A_1 \cdot S_1 + \Delta M + E \in \mathcal{R}_q.
$$
When we compute in $\mathcal{R}_q$, we do polynomial operations modulo $X^N+1$ and modulo $q$. To reduce modulo $X^N+1$, you can observe that $X^N = X^4 \equiv -1 \mod X^4 +1$. So:
$$
\begin{aligned}
A_0 \cdot S_0 &= (17 -2 X -24 X^2 + 9 X^3)\cdot (X+X^2) \\
&= 17  X + (17 - 2 )  X^2 + (-2 -24)  X^3 + (-24 +9)  X^4 + 9  X^5 \\
&= 17  X + 15 X^2 -26 X^3 + 15 - 9  X \\
&= 15 + 8 X + 15 X^2 -26 X^3 \in \mathcal{R}_q.
\end{aligned}
$$

‍

In the same way:
$$
A_1 \cdot S_1 =  (-14 -X^2 + 21 X^3) \cdot (1 + X^2 + X^3) = -13 - 20 X +28X^2 +7 X^3 \in \mathcal{R}_q.
$$
Observe that
$$
\Delta M = -32 + 16\cdot X+ 0\cdot X^2 - 16\cdot X^3 \in \mathcal{R}_q.
$$
Then:
$$
B = A_0 \cdot S_0 + A_1 \cdot S_1 + \Delta M + E = -31 +5 X -21 X^2 +30 X^3  \in \mathcal{R}_q.
$$

So the encryption is:
$$
(A_0, A_1, B) = (17 -2 X-24 X^2 + 9 X^3, -14 -X^2 + 21 X^3, -31 +5 X -21 X^2 +30 X^3) \in \mathcal{R}^3_q.
$$

When we decrypt, by computing $B - \sum_{i=0}^{k-1} A_i \cdot S_i \in \mathcal{R}_q$ we find
$$
31 +17 X -15 X^3.
$$
Then:
$$
\lfloor (31 +17 X -15 X^3)/16 \rceil = -2 + X -X^3 \in \mathcal{R}_p
$$
which is the message we encrypted. Decryption worked fine because the error coefficients were all smaller (in absolute value) than $\Delta/2 = 8$.

Trivial GLWE ciphertexts

In the next blog posts we will sometimes use what we call trivial GLWE ciphertexts. Those ciphertexts are not true encryptions, in the sense that they hide information, but must be seen more as placeholders: they have in fact the shape of a GLWE ciphertext but the message is in clear. A trivial ciphertext of a message $M$ has all the $A_i$ set to $0$ and the $B$ equal to $\Delta M$:

$$
(0, \ldots, 0, \Delta M) \in \mathcal{R}_q^{k+1}.
$$

No worries, we never use these ciphertexts to encrypt sensitive information of course! In the next blog posts we will show how to use them to inject publicly known data in homomorphic computations.

LWE and RLWE

Now you might wonder how we can obtain LWE and RLWE from GLWE ciphertexts.
When we instantiate GLWE with $k = n \in \mathbb{Z}$ and $N = 1$ we get LWE. Observe that $\mathcal{R}_q$ (resp. $\mathcal{R}$) is actually $\mathbb{Z}_q$ (resp. $\mathbb{Z}$) when $N = 1$.

When we instantiate GLWE with $k = 1$ and $N$ a power of 2 we get RLWE.

Public key encryption

In the previous section we showed you how to do secret key encryption. It is also possible to encrypt by using a public key. In practice, a public key would be a list of encryptions of zero (i.e. $M=0$). To encrypt a message, it is sufficient to take a random combination of these encryptions of zero and add the desired message $\Delta M$. Since we will not use public key encryption in this blog post series, we will not go into more details. But if you are curious about the subject, check this paper.

GLev

GLev ciphertexts have been used in FHE for a long time: in one of the following blog posts you will see them being largely used in some crucial FHE leveled operations. The name GLev was used for the first time in CLOT21 to be able to identify an intermediate type of ciphertext between GLWE and GGSW ciphertexts and make at the same time GGSW ciphertexts easier to understand. GLev can be seen as a generalization of the well known Powers of 2 encryptions used in BGV.

A GLev ciphertext contains redundancy: it is composed by a list of GLWE ciphertexts encrypting the same message $M$ with different, and very precise, scaling factors $\Delta$. Two parameters are necessary to define these special $\Delta$’s: a base $\beta$, generally a power of 2, and a number of levels $\ell \in \mathbb{Z}$:

$$
\left( GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^1} M\right) \times \ldots \times GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^\ell} M\right) \right) = GLev^{\beta, \ell}_{\vec{S}, \sigma}(M) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.
$$

If $\beta$ and $q$ are not powers of 2, a rounding should be applied at the moment of encoding. The secret key is the same as for GLWE ciphertexts. To decrypt, it is sufficient to decrypt one of the GLWE ciphertexts with the corresponding scaling factor. The set of GLev encryptions of the same message $M$, under the secret key $\vec{S}$, with Gaussian noise with standard deviation $\sigma$, with base $\beta$ and level $\ell$, will be noted $GLev^{\beta,\ell}_{\vec{S}, \sigma}(M)$.

Lev and RLev

In the same way we saw that GLWE was a generalization for both LWE and RLWE, we can observe that GLev can be specialized into Lev and RLev, by following the same rules.

GGSW

Now that we know what GLWE and GLev ciphertext are, GGSW will be very easy to understand. Let’s put it this way.

• A GLWE ciphertext is a vector of elements from $\mathcal{R}_q$ (or a 1 dimensional matrix),
• A GLev ciphertext is a vector of GLWE ciphertexts (or a 2 dimensional matrix of elements from $\mathcal{R}_q$),
• A GGSW ciphertext is a vector of GLev ciphertexts (or a 3 dimensional matrix of elements from $\mathcal{R}_q$, or a 2 dimensional matrix of GLWE ciphertexts).

With GGSW ciphertexts we once again add some redundancy thanks to a 3rd dimension in the structure.
In particular, in a GGSW, each GLev ciphertext encrypts the  product between $M$ and  one of the polynomials of the secret key $-S_i$. The last GLev in the list just encrypts the message $M$:

$$
\left( GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_0 M) \times \ldots \times GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_{k-1} M) \times GLev^{\beta, \ell}_{\vec{S}, \sigma}(M) \right) = GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}.
$$

The secret key is the same as for GLWE and GLev ciphertexts. To decrypt, it is sufficient to decrypt the last GLev ciphertext. The set of GGSW encryptions of the same message $M$, under the secret key $\vec{S}$, with Gaussian noise with standard deviation $\sigma$, with base $\beta$ and level $\ell$, will be noted $GGSW^{\beta,\ell}_{\vec{S}, \sigma}(M)$.

GSW and RGSW

In the same way we already saw for both GLWE and GLev, we can observe that GGSW can be specialized into GSW and RGSW, by following the same rules presented before.

Curious to know how we use these ciphertexts to build FHE operations? Read part II to get one step forward in the comprehension of the TFHE scheme by showing you how to use different encodings and how to use some basic homomorphic operations.
‍

‍
And a special thank you to Damien Ligier for the valuable feedback and editing of this blog post.

Additional links

• ⭐️ Like our work? Support us and star TFHE-rs on Github
• 👋 Questions? Join the Zama community.
• 💸 Join the Zama Bounty Program. Solve FHE problems, write tutorials and earn rewards, more than €500,000 in prizes.