TFHE Deep Dive - Part II - Encodings and linear leveled operations

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

‍In the previous blog post of the series, we have described the ciphertexts used in TFHE. In this post we will start discovering how to perform operations on these ciphertexts. In particular, we will describe two simple homomorphic operations: homomorphic addition and multiplication by unencrypted constants.

We will mainly focus on GLWE ciphertexts: since GLev and GGSW are composed by GLWE ciphertexts themselves, it will be easier in the end to see how the same operations are performed on them.

Note that most of the homomorphic operations have an impact on the noise. In this series of blog posts we will give intuitions on this noise growth  -- both in the text and in the figures (with little thermometers) -- but we will not enter into the details of noise analysis: for more information about the subject, we refer you to the TFHE and [CLOT21] papers.

We will also try to understand a little bit more about how messages are encoded and what the consequences are of this encoding on the result of homomorphic operations. Encodings are, in fact, an overlayer of the encryption and are extremely useful in FHE.

In this post we use the same notations as in the previous one.

GLWE homomorphic addition

Let $p$ and $q$ be two positive integers, such that $p\leq q$ and let’s define $\Delta = q/p$. As already mentioned in previous blog post, In TFHE $q$ and $p$ are often chosen to be powers of two, otherwise a rounding at the moment of encoding of messages should be applied.
Let’s recall that a GLWE ciphertext encrypting a message $M \in \mathcal{R}_p$ under the secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$ is a tuple:
$$
C = (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}$.

Now, let’s consider another GLWE ciphertext encrypting the message $M' \in \mathcal{R}_p$ under the same secret key $\vec{S} \in \mathcal{R}^k$:
$$
C' = (A'_0, \ldots, A'_{k-1}, B') \in GLWE_{\vec{S}, \sigma}(\Delta M') \subseteq \mathcal{R}_q^{k+1}
$$

Then, we can add every component of the two ciphertexts (in $\mathcal{R}_q$) and the result will be a new GLWE ciphertext encrypting the sum $M+M' \in \mathcal{R}_p$ under the same secret key $\vec{S}$, with noise that grew a little bit (additively with respect to the original noises in $C$ and $C'$) and that we will estimate with standard deviation $\sigma'$.

We note the homomorphic addition between ciphertexts with the symbol “$+$".

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

Toy example

To better understand GLWE addition, let's use a toy example as in previous blog post. Again, 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 also 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) = (X + X^2, 1 + X^2 + X^3) \in \mathcal{R}^2.
$$
Let’s encrypt two messages
$$
\begin{aligned}
M &= - 2 + X - X^3 &\in \mathcal{R}_p \\
M' &= X + X^2 -2X^3 &\in \mathcal{R}_p
\end{aligned}
$$
which are polynomials of degree smaller than $N$ with coefficients in $\{ -2, -1, 0, 1 \}$. Their addition in $\mathcal{R}_p$ is equal to
$$
M^{(+)} = -2 - 2X + X^2 + X^3 \in \mathcal{R}_p.
$$

Let's encrypt these messages: as shown in previous blog post,  we need to sample uniformly random polynomial masks with coefficients in $\{ -32, -31, \ldots,$ $ -1, 0, 1, 2, \ldots, 30, 31 \}$ and discrete Gaussian Errors (small coefficients):

Let's choose $\vec{A} = (A_0, A_1) = (17 -2 X- 24 X^2 + 9 X^3, -14 - X^2 + 21 X^3) \in \mathcal{R}_q^2$ and $E = -1 + X + X^3 \in \mathcal{R}_q$ as randomness for the first message.

Let's choose $\vec{A'} = (A'_0, A'_1) = (-8 +15 X +3 X^2 -30 X^3, 23 -16 X +27 X^2 -4 X^3) \in \mathcal{R}_q^2$ and $E' = X - X^2 - X^3 \in \mathcal{R}_q$ as randomness for the second message.

Then, we need to compute the bodies as:

$B = A_0 S_0 + A_1 S_1 + \Delta M + E = -31 +5 X -21 X^2 +30 X^3 \in \mathcal{R}_q$,

$B' = A'_0 S_0 + A'_1 S_1 + \Delta M' + E' = -25 +12 X^2 -12 X^3 \in \mathcal{R}_q$.

Recall that, when we compute in $\mathcal{R}_q$, we do polynomial operations modulo $X^N+1$ ($X^4 +1$ in this example) and modulo $q$ ($64$ in this example). So the encryptions are, respectively:

$$
C = (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
$$

and

$$
C' = (A'_0, A'_1, B') = (-8 +15 X +3 X^2 -30 X^3, 23 -16 X +27 X^2 -4 X^3, -25 +12 X^2 -12 X^3) \in \mathcal{R}^3_q
$$

Now, let's perform the homomorphic addition. To do so, we need to add in $\mathcal{R}_q$ the components term wise:

$A^{(+)}_0 = A_0 + A'_0 = 17 -2 X-24 X^2 + 9 X^3 -8 +15 X +3 X^2 -30 X^3 = 9 +13 X -21 X^2 -21 X^3 \in \mathcal{R}_q,$

$A^{(+)}_1 = A_1 + A'_1 = -14 -X^2 + 21 X^3 + 23 -16 X +27 X^2 -4 X^3 = 9 -16 X +26 X^2 + 17 X^3 \in \mathcal{R}_q,$

$B^{(+)} = B + B' = -31 +5 X -21 X^2 +30 X^3 -25 +12 X^2 -12 X^3 = 8 +5 X -9 X^2 +18 X^3 \in \mathcal{R}_q.$

So:
$$
C^{(+)} = (A^{(+)}_0, A^{(+)}_1, B^{(+)}) = (9 +13 X -21 X^2 -21 X^3, 9 -16 X +26 X^2 + 17 X^3, 8 +5 X -9 X^2 +18 X^3) \in \mathcal{R}^3_q
.$$

Let's now decrypt, to verify that the result is the correct one. To decrypt, we compute:
$$
B^{(+)} - \sum_{i=0}^{k-1} A^{(+)}_i \cdot S_i = 31 -30 X +15 X^2 +16 X^3 \in \mathcal{R}_q
$$

Then:
$$
\lfloor (31 -30 X +15 X^2 +16 X^3)/16 \rceil = -2 -2 X + X^2 + X^3 \in \mathcal{R}_p
$$
which is exactly $M^{(+)}$. Decryption worked fine because the error coefficients were all smaller (in absolute value) than $\Delta/2 = 8$. The new error was in fact equal to $E^{(+)} = -1 +2 X - X^2$.

GLWE homomorphic addition with a constant.

And what if you wanted to add a constant value to a GLWE ciphertext? In the previous blog post we talked about trivial GLWE ciphertexts, which are placeholders with the shape of a GLWE ciphertext and the message in clear. So if you want to add a constant $\Sigma \in \mathcal{R}_p$ to a GLWE encryption of a message $M$, all you have to do is homomorphically add (as we have seen in this section) the trivial ciphertext $(0, \ldots, 0, \Delta \Sigma) \in \mathcal{R}_q^{k+1}$ to the GLWE encryption of $M$. The result is going to be a GLWE encryption of $M + \Sigma$.

GLWE homomorphic multiplication by a constant

By following the same notations as the previous section, let's still consider a GLWE ciphertext encrypting a message $M \in \mathcal{R}_p$ under the secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$:
$$
C = (A_0, \ldots, A_{k-1}, B) \in GLWE_{\vec{S}, \sigma}(\Delta M) \subseteq \mathcal{R}_q^{k+1}.
$$
Let's now consider a small constant polynomial:
$$
\Lambda = \sum_{i=0}^{N-1} \Lambda_i X^i \in \mathcal{R}.
$$

Then, we can multiply the polynomial $\Lambda$ to every component of the ciphertext (in $\mathcal{R}_q$) and the result will be a new GLWE ciphertext encrypting the product $\Lambda \cdot M \in \mathcal{R}_p$ under the same secret key $\vec{S}$, with noise that grew a little bit (proportionally with respect to the size of the coefficients of $\Lambda$) and that we will estimate with standard deviation $\sigma^{\prime\prime}$.

We note the homomorphic multiplication of a ciphertext by a constant with the symbol "$\cdot$".

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

Observe that it is also possible to perform a multiplication with a small integer in $\mathbb{Z}$: the operation works in the same way, it is sufficient to observe that a small integer corresponds to a constant polynomial $\Lambda$, which means a polynomial where only the constant coefficient is different from $0$.

Toy example

To better understand GLWE multiplication by a small constant polynomial, let's use another toy example for the homomorphic addition.

Let’s choose the same parameters $q=64$, $p=4$, $\Delta = q/p = 16$, $N=4$ and $k =2$ and the same ciphertext
$$
C = (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
$$
encrypting a message $M = - 2 + X - X^3 \in \mathcal{R}_p$ under the secret key $\vec{S} = (S_0, S_1) = (X + X^2, 1 + X^2 + X^3) \in \mathcal{R}^2$, with a small error $E = -1 + X + X^3 \in \mathcal{R}_q$.

Then, for this example, let's choose a small constant polynomial
$$
\Lambda = -1 + 2 X^2 + X^3 \in \mathcal{R}.
$$

The multiplication between $M$ and $\Lambda$ in $\mathcal{R}_p$ is equal to
$$
M^{(\cdot)} = 1 + X + X^2 + X^3 \in \mathcal{R}_p.
$$
Now, let's perform the homomorphic multiplication by $\Lambda$. To do so, we need to multiply in $\mathcal{R}_q$ the components of the ciphertext $C$ times $\Lambda$:

$A^{(\cdot)}_0 = \Lambda \cdot A_0= (-1 + 2 X^2 + X^3) \cdot (17 -2 X-24 X^2 + 9 X^3) = -31 +8 X - 15 X^2 + 4 X^3 \in \mathcal{R}_q,$

$A^{(\cdot)}_1 = \Lambda \cdot A_1 = (-1 + 2 X^2 + X^3) \cdot (-14 -X^2 + 21 X^3) = 16 + 23 X + 16 X^2 + 29 X^3 \in \mathcal{R}_q,$

$B^{(\cdot)} = \Lambda \cdot B = (-1 + 2 X^2 + X^3) \cdot (-31 +5 X -21 X^2 +30 X^3) = 4 + 20 X - 7 X^2 +13 X^3 \in \mathcal{R}_q.$

So:
$$
C^{(\cdot)} = (A^{(\cdot)}_0, A^{(\cdot)}_1, B^{(\cdot)}) = (-31 +8 X - 15 X^2 + 4 X^3, 16 + 23 X + 16 X^2 + 29 X^3, 4 + 20 X - 7 X^2 +13 X^3) \in \mathcal{R}^3_q.
$$

Let's now decrypt to verify that the result is the correct one. To decrypt, we compute:
$$
B^{(\cdot)} - \sum_{i=0}^{k-1} A^{(\cdot)}_i \cdot S_i = 16 +13 X +13 X^2 +16 X^3 \in \mathcal{R}_q.
$$

Then:
$$
\lfloor (16 +13 X +13 X^2 +16 X^3)/16 \rceil = 1 + X + X^2 + X^3 \in \mathcal{R}_p
$$

which is exactly $M^{(\cdot)}$. Decryption worked fine because the error coefficients were all smaller (in absolute value) than $\Delta/2 = 8$. The new error was in fact equal to $E^{(\cdot)} = -3 X -3 X^2$.

GLev and GGSW homomorphic addition and multiplication by a constant

In previous blog post we observed that the GLev and GGSW ciphertexts are a collection of GLWE ciphertexts, containing some redundancy. In the next blog posts we will see why this redundancy is so important.

If we want to add together two GLev cipherexts or two GGSW ciphertexts, it will be sufficient to add together the corresponding GLWE ciphertexts composing them.

If we want to multiply a GLev cipherext or a GGSW ciphertext times a small constant polynomial $\Lambda$, it will be sufficient to multiply all the GLWE ciphertexts composing them times $\Lambda$.

GLWE encodings

When we encrypt messages, it is important to define an encoding. Roughly speaking, an encoding is the way we decide to represent a message inside the ciphertext. This is extremely important because it impacts the way homomorphic operations are performed.

There are many possible encodings, depending on the message type and on the way we want to perform homomorphic operations. We will analyze a few different types of encodings. Note that the list is not exhaustive, but at least it will give you an idea of the importance of encodings.

Encoding integers in the MSB

In TFHE, the noise is added in the LSB (least significant bits). For this reason, we have to use an encoding that positions the message away from it, and so in the MSB (most significant bits).
There are other FHE schemes that adopt the same approach (as instance B/FV and HEAAN/CKKS), while others encode the message in the LSB and the noise in the MSB (as instance BGV).

For simplicity, we will describe encodings for LWE ciphertexts. Remember that a LWE ciphertext is a special case of GLWE with $k = n \in \mathbb{Z}$ and $N = 1$.
This means that a LWE ciphertext encrypting a message $m \in \mathbb{Z}_p$ under the secret key $\vec{s} = (s_0, \ldots, s_{n-1}) \in \mathbb{Z}^n$ is a tuple
$$
(a_0, \ldots, a_{n-1}, b) \in LWE_{\vec{s}, \sigma}(\Delta m) \subseteq \mathbb{Z}_q^{n+1}
$$
such that the elements $a_i$ are uniform random elements in $\mathbb{Z}_q$ and $b = \sum_{i=0}^{n-1} a_i \cdot s_i + \Delta m + e \in \mathbb{Z}_q$, with $e$ the small noise sampled from a Gaussian distribution $\chi_\sigma$. The encoded quantity $\Delta m \in \mathbb{Z}_q$ is a plaintext, while $m$, the message is a cleartext. The plaintext plus the error can be visualized as follows:

In the example represented in the figure, we have $q = 2^{32}$, $p = 2^7$ and $\Delta = 2^{25}$. Each little rectangle in the figure represents a bit of information. The plaintext is in the MSB and the error in the LSB part. In this representation, the error is a positive value, but it would work in the same way even if the error was negative, thanks to the rounding in the decryption step.

Here we have to stop for a moment and take a step back. We used this encoding until here (and especially in previous blog post) just for simplicity and because it is the encoding that also helps us define GLev and GGSW ciphertexts. But LWE ciphertexts, and more generally GLWE ciphertexts, can support different types of encoding.

This specific encoding is especially practical to make leveled operations (additions and multiplications by constants) modulo $p$. In fact, if as instance you add two LWE ciphertexts encrypting two messages $m_1$ and $m_2$ encoded in the MSB with the same $\Delta$, the result is going to be a new LWE ciphertext encrypting $m_1 + m_2 \mod p$ encoded in the MSB with the same $\Delta$ as the inputs. Observe that the noise as well grows a little bit.

Encoding integers in the MSB with padding bits

We will soon discover that homomorphic operations can be "helped out" by the encoding chosen in the ciphertexts, or better, the choice of the encoding can be (and usually is) influenced by the homomorphic operations that we want to perform.

To better understand, we describe here the encoding of integers with padding bits. This encoding is largely used in TFHE and consists in encrypting the message in the MSB, similarly to what we have seen in previous paragraph, but to add some bits of padding (i.e., bits set to zero) in the MSB part, to "provide space" for leveled operations (such as the homomorphic addition and multiplication by constants).

Similarly to before, we still define $\Delta = q/p$ such that $p\leq q$. But this time the message is going to be in $\mathbb{Z}_{p'}$ with $p' < p$, instead of $\mathbb{Z}_{p}$.
The "empty space" between $p'$ and $p$ is called padding. To better understand, we will visualize it in the next figure, where we set $q = 2^{32}$, $p = 2^7$, $\Delta = 2^{25}$ and $p' = 2^5$. This means that we have 2 bits of padding in the MSB.

This specific encoding is especially practical to make exact leveled operations (additions and multiplications by constants). In fact, if as instance you add two LWE ciphertexts encrypting two messages $m_1$ and $m_2$ encoded in the MSB with the same $\Delta$ and say that you use $2$ bits of padding, the result is going to be a new LWE encrypting the exact addition $m_1 + m_2$ encoded in the MSB with the same $\Delta$ as the inputs and with $1$ bit of padding that has been eventually "consumed" after the addition. Observe that, as before, the noise as well grows a little bit.

Encoding of binaries in GB mode.

A well known example of encoding in the MSB with padding is the one used in Gate Bootstrapping. The gate bootstrapping is an homomorphic operation that evaluates binary gates on LWE ciphertexts encrypting bits. This operation is implemented in the TFHE lib and TFHE-rs as instance.

The messages encoded are bits and the $\Delta$ that is used is $q/4$, so there is $1$ bit of padding (as in the image above). The bit of padding is used to perform an exact linear combination (between the two input LWE ciphertexts and some constants) that will be followed by a bootstrapping to compute the final result.

Wait a second! We do not know how bootstrapping works yet! So let's report this discussion to one of the next blog posts.

Encoding of reals

The last encoding we present in this blog post is the encoding of reals in a fixed interval. This is a very special encoding, cause the message and the error become a single thing. Differently from previous encodings, the message $m$ occupies the entire space $\mathbb{Z}_q$ but the LSB are perturbed by some error $e$, which "approximates" the information. In practice, $m + e$ is close to the value of $m$: $m \approx m + e$, but this time there is no way to distinguish the exact value of $m$ because there is no $\Delta$ value helping do the separation with the error part.

This specific encoding is especially practical to evaluate approximate leveled operations (additions and multiplications by constants) up to a certain precision.

When using this encoding, the decryption changes: the first step in the decryption -- the computation $b - \sum_{i=0}^{n-1} a_i \cdot s_i \in \mathcal{R}_q$ -- remains the same, but the second step is replaced by a rounding or by the addition of a new random error in the LSB. For more details, please refer to this paper.

As we said before, this does not conclude the list of all possible encodings: the encodings we present in this blog post are not an exhaustive list, but a few examples that can help understand the scheme better.

Torus visualization

Do you know why TFHE is called this way? Well, the "FHE" part seems clear, but why the "T"? The T in TFHE stands for Torus, a mathematical structure that looks like a donut, as the one represented in the figure below. The torus is a nice way to visualize the encodings, alternative to the bit representation used until now.

In the figure we show the correspondence between the two representations -- torus and bit representation -- by using a toy example with $q = 2^6$, $p = 2^2$ and $\Delta = q/p = 2^4$, and highlighting in orange an example of encoding in the MSB.

Encodings in GLWE

Now that we made a quick tour on LWE encodings, let's try to go back to the general case on GLWE ciphertexts. While an LWE encrypts a single value, a GLWE can encrypt a polynomial modulo $X^N + 1$, which is composed by $N$ coefficients.

To generalize the encodings to GLWE then it is sufficient to apply the encodings that we have seen for LWE messages to all the $N$ coefficients of the GLWE message (as in the figure).
Easy right?

‍Curious to know how we build other homomorphic operations? Read part III to get one step forward in the comprehension of the TFHE scheme by showing you how to perform homomorphic multiplications, key switchings and other small building blocks to be ready to finally understand the bootstrapping in the following blog post.

And a special thank you to Loris Bergerat for his help with the toy examples.

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.