Ciphertext

GLWE ciphertext

• $p \lt q$, $p$ is plaintext modulus, $q$ is ciphertext modulus, $\Delta = q / p$ is scaling factor, typically $p, q$ are powers of two
• $M \in \mathcal{R}_p$ is a message
• Secret key is $(s_0, \dots, s_{k-1}) \in \mathcal{R}^k$ where the coefficients are sampled from uniform binary distribution
• $(a_0, \dots, a_{k-1}, b) \in \mathcal{R}_q^{k+1}$ is GLWE ciphertext where $(a_0, \dots, a_{k-1})$ is sampled uniformly from $\mathcal{R}_q^k$ and $b = \sum_{i=0}^{k-1} a_i \cdot s_i + \Delta M + e$ where $e \in \mathcal{R}_q$ is sampled from Gaussian distribution $\chi_{\sigma}$
• Decryption happens in two phase:
  • Given GLWE ciphertext $(a_0, \dots, a_{k-1}, b) \in \mathcal{R}_q^k$, $b - \sum_{i=0}^{k-1} a_i \cdot s_i = \Delta M + e$
  • Divide the result by $\Delta$ and do rounding, for decryption to be successful, the (infinity) norm of $e$ should be smaller than $\Delta / 2$

GLev ciphertext

For base $\beta$ and $l$, GLev ciphertext for the message $M$ is represented as following:

All GLWE ciphertexts are encrypted using the same secret key $(s_0, \dots, s_{k-1})$. The difference is that in GLev ciphertext, GLWE ciphertexts are not scaled by $\Delta$. For $j = 0, \dots, l-1$,

GGSW ciphertext

GGSW ciphertext for the message $M$ is given as the following:

Homomorphic addition

For two GLWE ciphertexts encrypting $M_1, M_2 \in \mathcal{R}_p$, the homomorphic addition of two ciphertexts is as follows:

Since $b = \sum_{i=0}^{k-1} a_i \cdot s_i + \Delta M_1 + e$ and $b' = \sum_{i=0}^{k-1} a_i' \cdot s_i + \Delta M_2 + e'$, $b+b' = \sum_{i=0}^{k-1} (a_i+a_i') \cdot s_i + \Delta (M_1 + M_2) + e + e'$. The resulting ciphertext is encryption of $M_1 + M_2$ with slightly bigger noise.

Homomorphic multiplication

First, let's consider the multiplication of GLWE ciphertext $GLWE_{\vec{s}, \sigma}(\Delta M) = (a_0, \dots, a_{k-1}, b)$ with the constant $\Lambda \in \mathcal{R}_q$ with small coefficients. Then the multiplication is as follows:

Since $b = \sum_{i=0}^{k-1} a_i \cdot s_i + \Delta M_1 + e$, $\Lambda \cdot b = \sum_{i=0}^{k-1} \Lambda \cdot a_i \cdot s_i + \Delta \Lambda \cdot M_1 + \Lambda \cdot e$.

Key switching

Let's first consider homomorphic multiplication of the message $M$ by the constant with large coefficients $\gamma \in \mathcal{R}_q$. Applying the same method as above would make the noise big enough to make decryption to fail. In order to handle this, consider the decomposition of $r \in \mathbb{Z}_q$ by base $\beta$ as following:

We will assume that $\beta^l=q$ for now. $r_1, \dots, r_l$ is smaller than $\beta$. For $\gamma \in \mathcal{R}_q$, one can decompose each coefficient as above, and then $\gamma = \sum_{i=1}^l \frac{q}{\beta^i} \cdot \gamma_i$ and $\gamma_i$ has small norm.

Now, consider GLev ciphertext of $M$, $(GLWE_{\vec{s}, \sigma}(\frac{q}{\beta} M), \dots, GLWE_{\vec{s}, \sigma}(\frac{q}{\beta^l} M))$. Since $\gamma = \gamma_1 \frac{q}{\beta} + \dots + \gamma_l \frac{q}{\beta^l}$ by the decomposition, $\gamma M = \gamma_1 \frac{q}{\beta} M + \dots + \gamma_l \frac{q}{\beta^l} M$. Thus, this can be obtained by $\langle Decomp^{\beta, l}(\gamma), GLev_{\vec{s}, \sigma}^{\beta, l}(M) \rangle$. However, since GLev ciphertext does not contain $\Delta$, it is not directly used as homomorphic multiplication.

Now let's consider key switching. Key switching is to replace the secret key that was used to encrypt GLWE ciphertext with another secret key without decryption.

For GLWE ciphertext $(a_0, \dots, a_{k-1}, b) \in GLWE_{\vec{s}, \sigma}(\Delta M)$, the following is key switching key:

What we want to do is $b - \sum_{i=0}^{k-1} a_i \cdot s_i = \Delta M + e$ without decryption.

External product

External product is defined as follows:

$c'$ is GLWE ciphertext of $m_1 m_2$.

Programmable Bootstrapping

The PBS of TFHE has input

• LWE ciphertext $(a, b = \langle a, s \rangle + e + \Delta \cdot m) \in \mathbb{Z}_q^{n+1}$ where $s \in \{0, 1\}^n$
• LUT encoded in $t \in \mathcal{R}_q$
  • LUT encodes the values $\Delta \cdot f(m) + e$ where $f: \mathcal{R}_q \rightarrow \mathcal{R}_q$, $|e| \lt \Delta / 2$
  • LUT has blocks of which the position corresponds to $\Delta \cdot m + e$
  • each element of LUT is embedded in each coefficient of $\mathcal{R}_q$ element by mod switching
• Bootstrapping secret key
  • GLWE ciphertext secret key $s' \in \mathcal{R}^k$
• Bootstrapping key
  • Collection of GGSW ciphertexts of each bit of LWE secret key ($s_i$) encrypted by $s'$
• Key switching key
  • GLev ciphertexts of bootstrapping secret key encrypted by $s$

The goal of PBS is to compute decryption procedure and evaluation of $f(m)$ homomorphically, which means to compute LWE ciphertext of $\Delta \cdot f(m)$ with small error than in input LWE ciphertext.

Step 0: Modulus switching

Input: LWE ciphertext $(a, b = \langle a, s \rangle + e + \Delta \cdot m) \in \mathbb{Z}_q^{n+1}$
Output: LWE ciphertext $(a, b = \langle a, s \rangle + e + \Delta \cdot m) \in \mathbb{Z}_{2N}^{n+1}$

Since LUT conceptually has $q/2$ or $q$ possible values (depending on the negacyclic property of LUT), we should properly embed these values into $\mathcal{R}_q$ element. Since $\mathcal{R}_q$ has $N$ coefficients and has negacyclic property, we multiply each element of LUT by $2N/q$ and embed the resulting values into coefficients. Also, we do the similar thing to LWE ciphertext to embed them into $\mathbb{Z}_{2N}^{n+1}$. We will keep the notation for $a, e, \Delta$, but should be aware that these values actually change after mod switching.

Step 1: Chain of CMux operations

Input: GLWE ciphertext of $t \cdot X^{-b}$ encrypted by secret key $s'$
Output: GLWE ciphertext of $t \cdot X^{-(\Delta \cdot m + e)} = t \cdot X^{-b + \sum_{i=0}^{n-1} a_i s_i}$ encrypted by secret key $s'$

At the first part of PBS, one should compute $X^{-(\Delta \cdot m + e)} = X^{-b+\langle a,s \rangle}$ (this holds trivially in $\mathcal{R}_q$ because the exponents are in mod $2N$). So how can homomorphically compute this? Since $b$ is public value, GLWE ciphertext of $X^{-b}$ is given first. Depending on the value of each $s_i \in \{0, 1\}$, one can multiply the GLWE ciphertext of $X^{a_i}$ or just skip multiplying. This is where CMux operation and bootstrapping key comes to play. Since bootstrapping key is the GGSW ciphertext of each $s_i$, it is given to CMux operation as selector, and two GLWE ciphertexts, each of encrypting $X^{-b+a_0}$ and $X^{-b}$. Then this CMux operation will compute $X^{-b+a_0 s_0}$. Applying CMux operation $n$ times, one can compute $X^{-b+\sum_{i=0}^{n-1} a_i s_i}$.

Step 2: Sample extraction

Input: GLWE ciphertext of $t \cdot X^{-(\Delta \cdot m + e)}$ encrypted by secret key $s'$
Output: LWE ciphertext of the constant coefficient of $t \cdot X^{-(\Delta \cdot m + e)} \in \mathcal{R}_q$ under secret key $(s'_{0, 0}, \dots, s'_{0, N-1}, \dots, s'_{k-1, 0}, \dots, s'_{k-1, N-1})$ which are the coefficients of $s' \in \mathcal{R}^k$

Since LUT is the encoding of the values $\Delta \cdot f(m) + e'$ in coefficients, GLWE ciphertext of $t \cdot X^{-(\Delta \cdot m + e)}$ has $\Delta \cdot f(m) + e'$ in its constant coefficient. Thus we should extract the constant coefficient of the ciphertext homomorphically.

Step 3: Key switching

Input: LWE ciphertext of $\Delta \cdot f(m) + e$ under secret key $(s'_{0, 0}, \dots, s'_{0, N-1}, \dots, s'_{k-1, 0}, \dots, s'_{k-1, N-1})$ which are the coefficients of $s' \in \mathcal{R}^k$
Output: LWE ciphertext of $\Delta \cdot f(m) + e'$ under secret key $s$

Finally, using key switching key, which is the collection of GLev ciphertexts of $s'_{i,j}$ under secret key $s$, we obtain the LWE ciphertext of $\Delta \cdot f(m) + e'$ under secret key $s$.

Below is the full description of PBS.

Next topic

In the next post, I will discuss about verifiable PBS using SNARK proof system.

Reference

[1] https://eprint.iacr.org/2024/451.pdf
[2] https://www.zama.ai/post/tfhe-deep-dive-part-4