TFHE Deep Dive - Part III - Key switching and leveled multiplications

> 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!

In the previous blog post we described how to perform homomorphic additions and homomorphic multiplications with small constants. We also described a few encodings used in TFHE.

In this post, we will continue describing some more leveled homomorphic operations and building blocks. The goal is to create a solid basis to be able to understand bootstrapping in the next blog post.

Homomorphic multiplication by a large constant

In the previous blog post we described the GLWE homomorphic multiplication by a small constant polynomial and we said that the noise grew proportionally with respect to the size of the coefficients of the polynomial.

But what happens if we try to multiply by a large constant polynomial?

To even simplify the understanding, let's suppose that the polynomial is a constant (only the constant coefficient is different from 0).

By following the same notations as before, 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 large constant $\gamma \in \mathbb{Z}_q$.

If we try to do the same as before, we multiply every component of the ciphertext by $\gamma$ (in $\mathcal{R}_q$). But now, as $\gamma$ is large and the noise grews proportionally with respect to its size, what happens is that the noise compromises the result cause it grows too much.

To solve this noise problem, we need to use a very easy trick, combining decomposition and inner products. The idea consists in taking the large constant, and to decompose it into a small base $\beta$:
$$
\gamma = \gamma_1 \frac{q}{\beta^1} + \gamma_2 \frac{q}{\beta^2}  + \ldots + \gamma_\ell \frac{q}{\beta^\ell}
$$
where the decomposed elements $\gamma_1, \ldots, \gamma_\ell$ are in $\mathbb{Z}_\beta$, and so they are small. We note $\mathsf{Decomp}^{\beta,\ell}(\gamma) = (\gamma_1, \ldots, \gamma_\ell)$. For simplicity, we will suppose that both $q$ and $\beta$ are powers of two. In practice we often chose them as powers of two, if they are not, a rounding should be applied.

As the elements of the decomposition are small, now we should be able to perform the multiplication with the ciphertext and have just a small impact on the noise. But, in order to obtain as a result the product of $\gamma$ and the message $M$ we need to be able to invert the decomposition, and so to recompose $\gamma$.

To do that, instead of multiplying the decomposed elements times a GLWE encryption of $M$, we multiply them times the GLev encryption of $M$, that, by definition, encrypts $M$ times different powers of the decomposition base:
$$
\overline{C} = (C_1, \ldots, C_\ell) \in \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)}.
$$

In practice, we will perform an inner-product-like operation, so we will multiply every element of the decomposition times the corresponding element of the GLev and then add them all together
$$
\langle \mathsf{Decomp}^{\beta,\ell}(\gamma), \overline{C} \rangle = \sum_{j=1}^\ell \gamma_j \cdot C_j \in GLWE_{\vec{S}, \sigma'}\left(\gamma \cdot M\right) \subseteq \mathcal{R}_q^{k+1}
$$
where $\sigma'$ is the new standard deviation of the noise.

In this case, the noise grows way slowly, since the multiplication times the small constants have a smaller impact on the noise, and the following addition as well.

There is just one problem here: the GLWE in output has no more $\Delta$, so the new message potentially occupies the entire space $\mathbb{Z}_q$. We do not use this operation by itself in practice, but we use it as a building block for more complex operations such as key switching and homomorphic multiplication between ciphertexts. We will talk about these operations in the rest of the post.

Approximate decomposition

In the figures that we just shown, we implicitly used an exact decomposition, or better we decomposed the constant with full precision (using $\beta^\ell = q$). But this is not always necessary: we could decide to do an approximate decomposition and decompose up to a fixed precision (using $\beta^\ell < q$). In practice this means that we will do a rounding in the LSB part before decomposing: if the decomposition parameters are chosen properly, this will not affect the correctness of the computations because in the LSB part there is always noise and the information we are interested into keeping -- the message -- is in the MSB part. This is actually very convenient in some of the homomorphic operations that we will describe in the following sections.

Multiplication by a large polynomial

Now multiplication by a large polynomial follows the same footprint: you decompose the polynomial into small polynomials  and then perform a polynomial inner product with the GLev. Assuming that the polynomial we want to decompose is $\Lambda = \sum_{i=0}^{N-1} \Lambda_i \cdot X^i$, then the decomposition is equal to:
$$
\mathsf{Decomp}^{\beta,\ell}(\Lambda) = (\Lambda^{(1)}, \ldots, \Lambda^{(\ell)})
$$
where $\Lambda^{(j)} = \sum_{i=0}^{N-1} \Lambda_{i,j} \cdot X^i$, with $\Lambda_{i,j} \in \mathbb{Z}_\beta$, such that:
$$
\Lambda = \Lambda^{(1)} \frac{q}{\beta^1} + \ldots + \Lambda^{(\ell)} \frac{q}{\beta^\ell}.
$$
If the decomposition is approximate, the equality becomes an approximation.

This operation is going to be the main building block operation to describe the key switching and the homomorphic multiplication in the following sections. But first, let's fix the ideas with a toy example.

Toy example

The goal of this toy example is not to perform a multiplication between a large constant and a ciphertext, but to fix ideas about the decomposition. In particular, we show how to decompose a large polynomial by using approximate signed decomposition, which is the one we mostly use in practice. For this toy example, we use our usual parameters $q=64$, $p=4$, $\Delta = q/p = 16$, $N=4$ and $k = 2$.

Now let's choose a random large polynomial in $\mathcal{R}_q$, so a polynomial of degree smaller than $N = 4$ and with coefficients in $\{ -32, -31, \ldots,$ $ -1, 0, 1, 2, \ldots, 30, 31 \}$:
$$
\Lambda = \Lambda_0 + \Lambda_1 X + \Lambda_2 X^2 + \Lambda_3 X^3 = 28 - 5 X - 30 X^2 + 17 X^3
$$
Let's choose a base for the decomposition $\beta = 4$ and $\ell = 2$, so $\beta^\ell = 16$. This means that we will decompose the $4$ MSB of each coefficient. But before we decompose, we need to round all the coefficients.

We start by writing them in their binary decomposition first (MSB on the left and LSB on the right), and by performing the rounding of the $2$ LSB:

• $\Lambda_0 = 28 \longmapsto (0, 1, 1, 1 {\color{red} |} 0, 0)$ which after rounding becomes $\Lambda'_0 \longmapsto (0, 1, 1, 1);$
• $\Lambda_1 = -5 \longmapsto (1, 1, 1, 0 {\color{red} |} 1, 1)$ which after rounding becomes $\Lambda'_1 \longmapsto (1, 1, 1, 1);$
• $\Lambda_2 = -30 \longmapsto (1, 0, 0, 0 {\color{red} |} 1, 0)$ which after rounding becomes $\Lambda'_2 \longmapsto (1, 0, 0, 1);$
• $\Lambda_3 = 17 \longmapsto (0, 1, 0, 0 {\color{red} |} 0, 1)$ which after rounding becomes $\Lambda'_3 \longmapsto (0, 1, 0, 0).$

Next step is the decomposition. We start from the LSB and, since the base $\beta = 4$, we need to extract $2$ bits at every round. We want the decomposition to be signed, so we want coefficients in $\{ -2, -1, 0, 1 \}$. So when in the binary decomposition we find $(0,0)$ -- corresponding to $0$ -- or $(0,1)$ -- corresponding to $1$ -- we simply read and record the value. When instead we find $(1,0)$ -- corresponding to $2$ -- or $(1,1)$ -- corresponding to $3$ -- we subtract $4$ to the block, and we add $+4$ to the next block in the decomposition, like a carry. Every carry that goes beyond the MSB, is thrown away. Let's do it in practice, it will be easier to understand.
‍

In $\Lambda'_0 \longmapsto (0, 1, 1, 1)$:

• The two LSB are $(1,1)$, corresponding to the value $3$. We subtract $4$ and obtain $3-4 = -1$ as the first element of the decomposition.

• The next block is $(0,1)$, but since we subtracted $4$ before, we need to add it back now, which corresponds to add $1$ to $(0,1)$, that becomes $(1,0)$, corresponding to the value $2$. As before we subtract $4$, obtaining $2-4 = -2$ as the second element of the decomposition. Since we reached the MSB, the $+4$ that should have been performed in the next block is simply thrown away.

In $\Lambda'_1 \longmapsto (1, 1, 1, 1)$:

• The two LSB are $(1,1)$, corresponding to the value $3$. We subtract $4$ and obtain $3-4 = -1$ as the first element of the decomposition.
• ‍The next block is $(1,1)$, but since we subtracted $4$ before, we need to add it back now, which corresponds to add $1$ to $(1,1)$, that becomes $(0,0)$, corresponding to the value $0$, which will be the second element of the decomposition.  

In $\Lambda'_2 \longmapsto (1, 0, 0, 1)$:

• The two LSB are $(0,1)$, corresponding to the value $1$, which will be the first element of the decomposition.
• The next block is $(1,0)$, corresponding to the value $2$. As before we subtract $4$, obtaining $2-4 = -2$ as the second element of the decomposition.  

In $\Lambda'_3 \longmapsto (0, 1, 0, 0)$:

• The two LSB are $(0,0)$, corresponding to the value $0$, which will be the first element of the decomposition.
• The next block is $(0,1)$, corresponding to the value $1$, which will be the second element of the decomposition.  

Now that the decomposition of the coefficients is done, we can write explicitly the decomposed polynomials as:
$$
\begin{cases}
\Lambda^{(1)} = -2 -2 X^2 + X^3 \\
\Lambda^{(2)} = -1 - X + X^2 \\
\end{cases}
$$
Observe that the coefficients of $\Lambda^{(2)}$ are the first elements of the decomposition, while the coefficients of $\Lambda^{(1)}$ are the second elements of the decomposition. These polynomials can be used now in the inner products with the GLev ciphertexts.

To verify that the decomposition is correct, we can invert it by computing:
$$
\Lambda^{(1)} \cdot \frac{q}{\beta^1} + \Lambda^{(2)} \cdot \frac{q}{\beta^2} = (-2 -2 X^2 + X^3) \cdot 16 + (-1 - X + X^2) \cdot 4 = 28 - 4 X - 28 X^2 + 16 X^3 \in \mathcal{R}_q
$$
which is, as expected, an approximation of the original polynomial $\Lambda$.

Key switching

At this point you might wonder if multiplying for a large constant (as large as the ciphertext modulo $q$) would be really useful in practice. The answer is yes, if the large constant is/are another ciphertext. Ciphertexts are in fact large vectors, polynomials, vectors of polynomials, and so on, composed by integers modulo $q$, that look uniformly random, so they might be quite large in general.

The trick combining decomposition and inner products with GLev ciphertexts, that we shown in previous paragraph, will now be very useful to start defining more complex operations, and in particular multiplications between ciphertexts.

The first operation, looking like a multiplication, that we will focus on, is called key switching. This is an homomorphic operation largely used in all the (Ring)LWE-based schemes and, as the name suggests, it is used to switch the secret key to a new one.

Let’s take 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}
$$
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}$, as we have already seen many times in previous blog posts.

Now, to switch the key we will try to cancel the secret key $\vec{S}$ and re-encrypt under a new secret key $\vec{S}'$, and we will try to do this homomorphically. The idea is to compute:
$$
B - \sum_{i=0}^{k-1} A_i \cdot S_i = \Delta M + E \in \mathcal{R}_q
$$
but instead of using the elements $S_i$ in clear, we will provide them encrypted under the new secret key $\vec{S}'$.

It is here that the multiplication between a ciphertext and a large constant comes to play: the ciphertext will be the GLev encryption of $S_i$ and the large constant will be $A_i$ that, by construction, is a uniformly random polynomial in $\mathcal{R}_q$.

Let's call key switching key the list of GLev encryptions of the secret key elements $S_i$ under the new secret key $\vec{S}'$, and let's note them as:
$$
\mathsf{KSK}_i \in \left( GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^1} S_i\right) \times \ldots \times GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^\ell} S_i\right) \right) = GLev^{\beta, \ell}_{\vec{S}', \sigma_{\mathsf{KSK}}}(S_i) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.
$$
In practice, the key switching is performed as follows:
$$
C' = \underbrace{\overbrace{(0, \ldots, 0, B)}^{\text{Trivial GLWE of } B} - \sum_{i=0}^{k-1} \overbrace{ \langle \mathsf{Decomp}^{\beta,\ell}(A_i), \mathsf{KSK}_i \rangle}^{\text{GLWE encryption of } A_i S_i} }_{\text{GLWE encryption of } B - \sum_{i=0}^{k-1} A_i S_i = \Delta M + E}\in GLWE_{\vec{S}', \sigma'}(\Delta M) \subseteq \mathcal{R}_q^{k+1}.
$$
The secret key has switched from $\vec{S}$ to $\vec{S}'$ but the message is the same.

Observe that this corresponds to the homomorphic evaluation of the first step of the GLWE decryption, but since we do not evaluate the second step -- which is the re-scaling by $\Delta$ and rounding -- we do not reduce the noise. On the contrary, the noise in the result of the operation is larger than the one in the input ciphertext $C$, and we note it $\sigma'$.

Various types of key switching

There exists various types of key switching that we use in practice. Some examples (not an exhaustive list) are the:
‍

• Key switching from one LWE to one LWE,

• Key switching from one RLWE to one RLWE,

• Key switching from one LWE to one RLWE, putting the message encrypted in the LWE into one of the coefficients of the RLWE ciphertext,

• Key switching from many LWE to one RLWE, packing the messages encrypted in the many LWE inputs into the RLWE ciphertext.

Other uses of the key switching

The key switching is not only used to switch the key, but can be also used to switch the parameters. In fact, the output key could be defined with $N$ and $k$ parameters that might be different from the ones of the input key. This is actually something that happens very often in the key switching: a practical example (involved in the bootstrapping) will be shown in next blog post: stay tuned!

External product

Now that we know how to perform a key switching, the external product operation will be straight forward.

With the external product our goal would be to homomorphically multiply two ciphertexts such that the result is an encryption of the product of messages.

What we know, until here, is that to multiply a large constant to a ciphertext, we need to decompose the large constant and recompose by using a GLev as a ciphertext. We also know that a GLWE ciphertext is a list of large constants. So how to combine these two ideas to do multiplication?

We will use a similar approach as the one used for key switching, so we will take one of the two ciphertexts as a GLWE (the ciphertext we will decompose), and the other ciphertext will be a list of GLev ciphertexts. The difference, this time, is that with key switching we wanted only the mask of the first ciphertext to be multiplied by the GLev's encrypting the secret key, while this time we want both mask and body.

In the first blog post we introduced a ciphertext, composed by GLev ciphertexts, that is just right for us: GGSW.

So, to summarize, the external product we will build is an operation that allows to multiply two ciphertexts -- a GLWE and a GGSW -- and that returns in output a new ciphertext -- a GLWE one -- encrypting the product of the two messages encrypted in the inputs. The two inputs are:
‍

• a GLWE ciphertext encrypting a message $M_1 \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_1) \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}$, as we have already seen before.
• a GGSW ciphertext encrypting a message $M_2 \in \mathcal{R}_p$ under the same secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$:
  $$
  \overline{\overline{C}} = (\overline{C}_0, \ldots, \overline{C}_{k-1}, \overline{C}_k) \in GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M_2) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}
  $$
  where $\overline{C}_i \in GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_i M_2)$ for $i \in [0..k-1]$ and $\overline{C}_k \in GLev^{\beta, \ell}_{\vec{S}, \sigma}(M_2)$.
  

Then the external product is noted with the symbol $\boxdot$ and is computed as:
$$
\begin{aligned}
C' &= \overline{\overline{C}} \boxdot C
= \langle \mathsf{Decomp}^{\beta,\ell}(C), \overline{\overline{C}} \rangle \\
&= \underbrace{
\overbrace{\langle \mathsf{Decomp}^{\beta,\ell}(B), \overline{C}_k \rangle}^{\text{GLWE encrypt. of } B M_2} + \sum_{i=0}^{k-1} \overbrace{\langle \mathsf{Decomp}^{\beta,\ell}(A_i), \overline{C}_i \rangle}^{\text{GLWE encrypt. of } - A_i S_i M_2}
}_{\text{GLWE encrypt. of } B M_2 - \sum_{i=0}^{k-1} A_i S_i M_2 \approx \Delta M_1 M_2}
\in GLWE_{\vec{S}, \sigma^{\prime\prime}}(\Delta M_1 M_2) \subseteq \mathcal{R}_q^{k+1}
\end{aligned}
$$
The noise in the result of the operation is larger than the one in the input ciphertext $C$, and we note it $\sigma^{\prime\prime}$.

External Product vs. Key Switching

A few more observations on differences and similarities between key switching and external product:
‍

• The external product is like a key switching with an additional element to the key switching key (the $\overline{C}_k$ GLev ciphertext).
• The external product is like a key switching where we do not switch the key. In fact, in the GGSW ciphertext, the secret key used for encryption and the one used inside the GLev ciphertexts are the same.
• An external product that takes as input a GGSW ciphertext, that uses a different secret key for encryption (say $\vec{S}'$) and uses the same secret key $\vec{S}$ as the GLWE ciphertext inside the encryption, is called functional key switching. In fact it applies a function (multiplication by an encrypted constant) and switches the key at the same time.  
  

Internal product

The external product is called external because is a product on GLWE that needs an external GGSW ciphertext to work (the external product notation is as instance used in mathematics for module over rings, which are abelian groups with an external law). There is no internal product between GLWE ciphertexts, or at least not one that could be done in a straight way. In B/FV, as instance, a product between GLWE ciphertexts is performed but it requires a key-switching-like operation.

There exists, however, an internal product between GGSW ciphertexts that can be defined from the external product. In fact, a GGSW ciphertext is a list of Glev ciphertexts, and each GLev is a list of GLWE ciphertexts. So, in practice, a GGSW is a list of GLWE ciphertexts. Since the external product is a product between GLWE and GGSW ciphertexts, we can define the internal product as a list of independent external products between one of the GGSW ciphertexts in input and all the GLWE ciphertexts composing the second GGSW input. The result of all these external products are going to be the GLWE ciphertexts that will compose the GGSW output.

To be more explicit, the internal product takes in input:
‍

• a GGSW ciphertext encrypting a message $M_1 \in \mathcal{R}_p$ under a secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$:
  $$
  \overline{\overline{C}}_1 = (\overline{C}_0, \ldots, \overline{C}_{k-1}, \overline{C}_k) \in GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M_1) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}.
  $$
  where, for $i \in [0..k-1]$:
  $$
  \overline{C}_i = (C_{i,1}, \ldots, C_{i,\ell}) \in GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_i M_1) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}
  $$
  with $C_{i,j} \in GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^j} (-S_i M_1) \right)$ for $j \in [1..\ell]$, and:
  $$
  \overline{C}_k \in (C_{k,1}, \ldots, C_{k,\ell}) \in GLev^{\beta, \ell}_{\vec{S}, \sigma}(M_1) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}
  $$
  with $C_{k,j} \in GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^j} M_1 \right)$ for $j \in [1..\ell]$.
• a GGSW ciphertext encrypting a message $M_2 \in \mathcal{R}_p$ under the same secret key $\vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^k$:
  $$
  \overline{\overline{C}}_2 \in GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M_2) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}.
  $$
  

Then the internal product is noted with the symbol $\boxtimes$ and is computed as:
$$
\overline{\overline{C}}' = \overline{\overline{C}}_2 \boxtimes \overline{\overline{C}}_1
= (\overline{\overline{C}}_2 \boxdot C_{0,1},
\ldots,
\overline{\overline{C}}_2 \boxdot C_{0,\ell},
\ldots,
\overline{\overline{C}}_2 \boxdot C_{k,1},
\ldots,
\overline{\overline{C}}_2 \boxdot C_{k,\ell}).
$$
Observe that:
$$
\left\lbrace
\begin{aligned}
\overline{\overline{C}}_2 \boxdot C_{i,j} &\in GLWE_{\vec{S}, \sigma^{\prime\prime}}\left( \frac{q}{\beta^j} (-S_i M_1 M_2) \right) &\text{for } i \in [0..k-1], j \in [1..\ell] \\
\overline{\overline{C}}_2 \boxdot C_{k,j} &\in GLWE_{\vec{S}, \sigma^{\prime\prime}}\left( \frac{q}{\beta^j} (M_1 M_2) \right) &\text{for } j \in [1..\ell]
\end{aligned}
\right.
$$
Then:
$$
\left\lbrace
\begin{aligned}
\left( \overline{\overline{C}}_2 \boxdot C_{i,1}, \ldots, \overline{\overline{C}}_2 \boxdot C_{i,\ell} \right) &\in GLev^{\beta, \ell}_{\vec{S}, \sigma^{\prime\prime}}\left( -S_i M_1 M_2 \right) &\text{for } i \in [0..k-1] \\
\left( \overline{\overline{C}}_2 \boxdot C_{k,1}, \ldots, \overline{\overline{C}}_2 \boxdot C_{k,\ell} \right) &\in GLev^{\beta, \ell}_{\vec{S}, \sigma^{\prime\prime}}\left( M_1 M_2 \right) &
\end{aligned}
\right.
$$
So, putting everything together, we observe that:
$$
\overline{\overline{C}}' = \overline{\overline{C}}_2 \boxtimes \overline{\overline{C}}_1
\in GGSW^{\beta, \ell}_{\vec{S}, \sigma^{\prime\prime}}(M_1 M_2) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}.
$$
The noise in the result of the operation is larger than the one in the input ciphertext $C$, and we note it $\sigma^{\prime\prime}$ (the same as the one in the external product).

Internal Product vs. External Product

The external product is way more efficient than the internal product, but it is not composable. This means that the result of an internal product can be used as input of another internal product, but the result of an external product (GLWE ciphertext) can be used only in one of the two inputs of another external product (the GLWE one) but not on the other (the GGSW one). So, if we use external products, the GGSW input should be a fresh one (just encrypted).

TFHE proposes a technique to build a GGSW ciphertext homomorphically from LWE, called circuit bootstrapping: we will not describe this technique in this series of blog posts, but if you are curious to know more about it, you can check this paper.

In TFHE, we use mainly the external product and avoid as much as possible the internal one.

CMux

Before we finish, let us describe a last operation, maybe the one that is mainly used in TFHE, and which will be one of the main building blocks of bootstrapping: the CMux operation.

The CMux operation is the homomorphic version of a Mux gate, also known as multiplexer gate. A Mux gate is, in practice, an if condition: it takes three inputs, a selector (a bit $b$ in the figure below) and two options ($d_0$ and $d_1$ in the figure below), and, depending on the value of the selector, it makes a choice between the two options.

It is evaluated in clear by computing:
$$
b \cdot (d_1 - d_0) + d_0 = d_b
$$

To evaluate it homomorphically, we encrypt $b$ as a GGSW ciphertext, and $d_0$ and $d_1$ as GLWE ciphertexts. Then the multiplication in the cleartext formula is evaluated as an external product, while the other operations (addition and subtraction) are evaluated as homomorphic additions and subtractions. The result, encrypting $d_b$ is a GLWE ciphertext.

This blog post was more challenging than the ones before. If you made it until here, congratulations! Are you still curious to know how we use all these operations to build bootstrapping? Read part IV to understand the bootstrapping of TFHE.

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.