GLWE Ciphertext-to-Ciphertext Addition

Suppose we have two GLWE ciphertexts encrypting two different plaintexts

M^{⟨ 1 ⟩}, M^{⟨ 2 ⟩}

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 1 ⟩}) = C^{⟨ 1 ⟩} = (A_{1}^{⟨ 1 ⟩}, A_{2}^{⟨ 1 ⟩}, . . . A_{k - 1}^{⟨ 1 ⟩}, B^{⟨ 1 ⟩}) \in R_{⟨ n, q ⟩}^{k + 1}

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 2 ⟩}) = C^{⟨ 2 ⟩} = (A_{1}^{⟨ 2 ⟩}, A_{2}^{⟨ 2 ⟩}, . . . A_{k - 1}^{⟨ 2 ⟩}, B^{⟨ 2 ⟩}) \in R_{⟨ n, q ⟩}^{k + 1}

C^{⟨ 1 ⟩} + C^{⟨ 2 ⟩} = (A_{1}^{⟨ 1 ⟩} + A_{1}^{⟨ 2 ⟩}, A_{2}^{⟨ 1 ⟩} + A_{2}^{⟨ 2 ⟩}, . . . A_{k - 1}^{⟨ 1 ⟩} + A_{k - 1}^{⟨ 2 ⟩}, B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩})

$⟨$ Summary C-1 $⟩$ GLWE Homomorphic Addition

${𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 1 ⟩}) + {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 2 ⟩})$

$= ({A_{i}^{⟨ 1 ⟩}}_{i = 0}^{k - 1}, B^{⟨ 1 ⟩}) + ({A_{i}^{⟨ 2 ⟩}}_{i = 0}^{k - 1}, B^{⟨ 2 ⟩})$

$= ({A_{i}^{⟨ 1 ⟩} + A_{i}^{⟨ 2 ⟩}}_{i = 0}^{k - 1}, B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩})$

$= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}))$

This means that adding two TFHE ciphertexts and decrypting the resulting ciphertext gives the same effect as adding two original (

Δ

-scaled) plaintexts:

Δ M^{⟨ 1 ⟩} + Δ M^{⟨ 2 ⟩} = Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩})

Proof.

1.: Define the following notations:
$A_{1}^{⟨ 3 ⟩} = A_{1}^{⟨ 1 ⟩} + A_{1}^{⟨ 2 ⟩}$
$A_{2}^{⟨ 3 ⟩} = A_{2}^{⟨ 1 ⟩} + A_{2}^{⟨ 2 ⟩}$
...
$A_{k - 1}^{⟨ 3 ⟩} = A_{k - 1}^{⟨ 1 ⟩} + A_{k - 1}^{⟨ 2 ⟩}$
$E^{⟨ 3 ⟩} = E^{⟨ 1 ⟩} + E^{⟨ 2 ⟩}$
$B^{⟨ 3 ⟩} = B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩}$
2.: Derive the following:
$B^{⟨ 3 ⟩} = B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩}$
$= \sum_{i = 0}^{k - 1} (A_{i}^{⟨ 1 ⟩} \cdot S_{i}) + Δ \cdot M^{⟨ 1 ⟩} + E^{⟨ 1 ⟩} + \sum_{i = 0}^{k - 1} (A_{i}^{⟨ 2 ⟩} \cdot S_{i}) + Δ \cdot M^{⟨ 2 ⟩} + E^{⟨ 2 ⟩}$
$= \sum_{i = 0}^{k - 1} ((A_{i}^{⟨ 1 ⟩} + A_{i}^{⟨ 2 ⟩}) \cdot S_{i}) + Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}) + (E^{⟨ 1 ⟩} + E^{⟨ 2 ⟩})$ # commutative and distributive rules
$= \sum_{i = 0}^{k - 1} (A_{i}^{⟨ 3 ⟩} \cdot S_{i}) + Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}) + E^{⟨ 3 ⟩}$
3.: Since $B^{⟨ 3 ⟩} = \sum_{i = 0}^{k - 1} (A_{i}^{⟨ 3 ⟩} \cdot S_{i}) + Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}) + E^{⟨ 3 ⟩}$ ,
this means that $(A_{1}^{⟨ 3 ⟩}, A_{2}^{⟨ 3 ⟩}, . . . A_{k - 1}^{⟨ 3 ⟩}, B^{⟨ 3 ⟩})$ form the ciphertext: ${𝖦𝖫𝖶𝖤}_{S, σ} (Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}))$ .
4.: Thus,
$= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 1 ⟩}) + {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 2 ⟩})$
$= (A_{1}^{⟨ 1 ⟩} + A_{1}^{⟨ 2 ⟩}, A_{2}^{⟨ 1 ⟩} + A_{2}^{⟨ 2 ⟩}, . . . A_{k - 1}^{⟨ 1 ⟩} + A_{k - 1}^{⟨ 2 ⟩}, B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩})$
$= (A_{1}^{⟨ 3 ⟩}, A_{2}^{⟨ 3 ⟩}, . . . A_{k - 1}^{⟨ 3 ⟩}, B^{⟨ 3 ⟩})$
$= ({A_{i}^{⟨ 3 ⟩}}_{i = 0}^{k - 1}, B^{⟨ 3 ⟩})$
$= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}))$

□

C-1 GLWE Ciphertext-to-Ciphertext Addition