GLWE Ciphertext-to-Ciphertext Addition

Suppose we have two GLWE ciphertexts encrypting two different plaintexts

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

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

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

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

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

${𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 1 ⟩} + E^{⟨ 1 ⟩}) + {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 2 ⟩} + E^{⟨ 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 ⟩}) + E^{⟨ 3 ⟩})$ $▹$ where $E^{⟨ 3 ⟩} = E^{⟨ 1 ⟩} + E^{⟨ 2 ⟩}$

This means that adding two GLWE ciphertexts (each of which encrypts

M^{⟨ 1 ⟩}

and

M^{⟨ 2 ⟩}

) and decrypting the resulting ciphertext yields

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

Proof.

1.: Define the following notations:
$A_{0}^{⟨ 3 ⟩} = A_{0}^{⟨ 1 ⟩} + A_{0}^{⟨ 2 ⟩}$
$A_{1}^{⟨ 3 ⟩} = A_{1}^{⟨ 1 ⟩} + A_{1}^{⟨ 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_{0}^{⟨ 3 ⟩}, A_{1}^{⟨ 3 ⟩}, A_{2}^{⟨ 3 ⟩}, . . . A_{k - 1}^{⟨ 3 ⟩}, B^{⟨ 3 ⟩})$ form the ciphertext: ${𝖦𝖫𝖶𝖤}_{S, σ} (Δ \cdot (M^{⟨ 1 ⟩} + M^{⟨ 2 ⟩}) + E^{⟨ 3 ⟩})$ .
4.: Thus,
${𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 1 ⟩} + E^{⟨ 1 ⟩}) + {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M^{⟨ 2 ⟩} + E^{⟨ 2 ⟩})$
$= (A_{0}^{⟨ 1 ⟩} + A_{0}^{⟨ 2 ⟩}, A_{1}^{⟨ 1 ⟩} + A_{1}^{⟨ 2 ⟩}, . . . A_{k - 1}^{⟨ 1 ⟩} + A_{k - 1}^{⟨ 2 ⟩}, B^{⟨ 1 ⟩} + B^{⟨ 2 ⟩})$
$= (A_{0}^{⟨ 3 ⟩}, 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 ⟩}) + E^{⟨ 3 ⟩})$

□

C-1 GLWE Ciphertext-to-Ciphertext Addition