GLWE Ciphertext-to-Plaintext Addition

Suppose we have a GLWE ciphertext ct and a new plaintext polynomial

Λ

as follows:

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

$⟨$ Summary C-2 $⟩$ GLWE Homomorphic Addition with a Plaintext

${𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E) + Δ Λ$

$= ({A_{i}}_{i = 0}^{k - 1}, B) + Δ Λ$

$= ({A_{i}}_{i = 0}^{k - 1}, B + Δ Λ)$

$= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ (M + Λ) + E)$

This means that adding a (

Δ

-scaled) plaintext polynomial

Λ

to a GLWE ciphertext that encrypts

M

and decrypting it yields

M + Λ

Proof.

1.

Since

B = \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ \cdot M + E

$B + Δ \cdot Λ = \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ \cdot M + E + Δ \cdot Λ = \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ \cdot (M + Λ) + E$

This means that $(A_{0}, A_{1}, . . . A_{k - 1}, B + Δ Λ)$ form the ciphertext ${𝖦𝖫𝖶𝖤}_{S, σ} (Δ (Λ + M) + E)$

2.

Thus,

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E) + Δ Λ

= (A_{0}, A_{1}, . . . A_{k - 1}, B + Δ Λ)

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

= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ (M + Λ) + E)

□

Noise Growth: Note that after decryption, the original ciphertext

𝖼𝗍 + Δ Λ

’s noise

E

stays the same as before. This means that ciphertext-to-plaintext addition does not increase the noise level.

C-2 GLWE Ciphertext-to-Plaintext Addition