Encryption and Decryption

TFHE encrypts and decrypts ciphertexts based on the LWE cryptosystem (§B-2), which is equivalent to the GLWE cryptosystem (§B-4) with

n = 1

. However, one distinction from the LWE cryptosystem is that TFHE samples the secret key elements from the binary set

{0, 1}

, not from the ternary set

{- 1, 0, 1}

$⟨$ Summary D-1.1 $⟩$ TFHE Encryption and Decryption

Initial Setup: $Δ = \frac{q}{t}$ , $\vec{s} \leftarrow_{}^{$} ℤ_{2}^{k}$ $▹$ where $t$ divides $q$ , and each element of $\vec{s}$ is a 0-degree polynomial

Encryption Input: $m \in ℤ_{t}$ , $\vec{a} \leftarrow_{}^{$} ℤ_{q}^{k}$ , $e \leftarrow_{}^{χ_{σ}} ℤ_{q}$ $▹$ each element of $\vec{a}$ is a 0-degree polynomial

1.: Scale up $m \to Δ \cdot m \in ℤ_{q}$
2.: Compute $b = \vec{a} \cdot \vec{s} + Δ m + e mod q$
3.: ${𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m + e) = (\vec{a}, b) \in ℤ_{q}^{k + 1}$

Decryption Input: $𝖼𝗍 = (\vec{a}, b) \in ℤ_{q}^{k + 1}$

1.: ${𝖫𝖶𝖤}_{\vec{s}, σ}^{- 1} (𝖼𝗍) = b - \vec{a} \cdot \vec{s} = Δ m + e (𝑚𝑜𝑑 q)$
2.: Scale down $⌈ \frac{Δ m + e}{Δ} ⌋ = m \in ℤ_{t}$ $▹$ i.e., modulus switch from $q \to t$

Condition for Correct Decryption:

The noise $e$ grown over homomorphic operations should be: $e < \frac{Δ}{2}$ .

In this section, we will often write

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m + e)

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m)

for simplicity, because

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m + e) \approx {𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m)

(i.e., they decrypt to the same message). Even in the case that we write

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m)

instead of

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m + e)

, you should assume this as an encryption of

Δ m + e

(i.e., the noise is included inside the scaled message).

D-1.1 Encryption and Decryption