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.
the ring of integer polynomials modulo the cyclotomic polynomial , with power of 2. In practice, it contains integer polynomials up to degree . , i.e., the same ring of integers as above, but this time the coefficients are modulo . Observe that we often note as .- Our modular reductions are centered around zero. As an example, when reducing modulo
, we use the congruence classes . is a Gaussian probability distribution with mean and standard deviation . If , we will simply note .- We will use small letters for (modular) integers
, we will use capital letters for polynomials . - We will note the list of integer elements from
to included, as . - We use the abbreviations MSB and LSB for Most Significant Bit and Least Significant Bit respectively.
- We denote with
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
In particular, the coefficients of the
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
where the elements
We often call

Now, if we have a ciphertext
1.
2.

Observe that the message

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
We sample the secret key with uniform binary distribution as
Let’s encrypt a message
In order to encrypt the message, we need to sample a uniformly random mask with coefficients in
and a discrete Gaussian Error (small coefficients):
To encrypt, we need to compute the body as :
When we compute in
In the same way:
Observe that
Then:
So the encryption is:
When we decrypt, by computing
Then:
which is the message we encrypted. Decryption worked fine because the error coefficients were all smaller (in absolute value) than
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
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

When we instantiate GLWE with

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.
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
If

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
(or a 1 dimensional matrix), - A GLev ciphertext is a vector of GLWE ciphertexts (or a 2 dimensional matrix of elements from
), - A GGSW ciphertext is a vector of GLev ciphertexts (or a 3 dimensional matrix of elements from
, 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
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

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.