GLWE Ciphertext-to-Plaintext Multiplication

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

Λ \cdot 𝖼𝗍 = (Λ \cdot A_{0}, Λ \cdot A_{1}, . . . Λ \cdot A_{k - 1}, Λ \cdot B)

We assume that we always do polynomial-to-polynomial multiplications efficiently in

O (n \log n)

by using the NTT technique (§A-16). Then, the following is true:

$⟨$ Summary C-3 $⟩$ GLWE Ciphertext-to-Plaintext Multiplication

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

$= Λ \cdot ({A_{i}^{⟨ 1 ⟩}}_{i = 0}^{k - 1}, B^{⟨ 1 ⟩})$

$= ({Λ \cdot A_{i}^{⟨ 1 ⟩}}_{i = 0}^{k - 1}, Λ \cdot B^{⟨ 1 ⟩})$

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

This means that multiplying a plaintext polynomial

Λ

by a GLWE ciphertext that encrypts

M

and decrypting it yields

M \cdot Λ

Proof.

1.: Define the following notations:
$A_{0}^{'} = Λ \cdot A_{0}$
$A_{1}^{'} = Λ \cdot A_{1}$
$...$
$A_{k - 1}^{'} = Λ \cdot A_{k - 1}$
$E^{'} = Λ \cdot E$
$B^{'} = Λ \cdot B$
2.: Derive the following:
$B^{'} = Λ \cdot B$
$= Λ \cdot (\sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ \cdot M + E)$ $= \sum_{i = 0}^{k - 1} (Λ \cdot A_{i} \cdot S_{i}) + Δ \cdot Λ \cdot M + Λ \cdot E$
$▹$ by the distributive property of a polynomial ring
$= \sum_{i = 0}^{k - 1} ((Λ \cdot A_{i}) \cdot S_{i}) + Δ \cdot (Λ \cdot M) + (Λ \cdot E)$
$= \sum_{i = 0}^{k - 1} (A_{i}^{'} \cdot S_{i}) + Δ \cdot (Λ \cdot M) + (E^{'})$
3.: Since $B^{'} = \sum_{i = 0}^{k - 1} (A_{i}^{'} \cdot S_{i}) + Δ \cdot (Λ \cdot M) + (E^{'})$ ,
$(A_{0}^{'}, A_{1}^{'}, . . . A_{k - 1}^{'}, B^{'})$ form the ciphertext ${𝖦𝖫𝖶𝖤}_{S, σ} (Δ \cdot Λ \cdot M)$ .
4.: Thus,
$Λ \cdot {𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E)$
$= (Λ \cdot A_{0}, Λ \cdot A_{0}, A_{1}, . . . Λ \cdot A_{k - 1}, Λ \cdot B)$
$= ({A_{i}^{'}}_{i = 0}^{k - 1}, Λ \cdot B)$
$= {𝖦𝖫𝖶𝖤}_{S, σ} (Δ (M \cdot Λ) + Λ \cdot E)$

□

If we decrypt

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

by using

S

, then we get the plaintext

Λ \cdot M

. Meanwhile,

A_{0}^{'}, A_{1}^{'}, . . . A_{k - 1}^{'}, E^{'}

get eliminated by rounding during decryption, regardless of whatever their values were randomly sampled during encryption.

The noise is a bigger problem now, because after decryption, the original ciphertext ct’s noise has increased from

E

E^{'} = Λ \cdot E

. This means that if we continue multiplication computations without decrypting the ciphertext to eliminate the noise

E^{'}

, it will continue growing more and eventually the noise in the lower bit area in

B

will overflow to the scaled plaintext bit area. If this happens, the noise

E^{'}

won’t be eliminated during decryption, ending up corrupting the plaintext

M

. Therefore, if the constant

Λ

is big, it is recommended to use gadget decomposition (§A-6.4), which we will explain in the next subsection.