C-3 GLWE Ciphertext-to-Plaintext Multiplication

- Reference: TFHE Deep Dive - Part II - Encodings and linear leveled operations [8]

Suppose we have a GLWE ciphertext $C$:

$C={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(M)=(A_1,A_2,...A_{k-1},B)\in R_{⟨n,q⟩}^{k+1}$

and a new plaintext polynomial $\mathrm{\Lambda }$ as follows:

$\mathrm{\Lambda }=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}({\mathrm{\Lambda }}_i\cdot X_i)\in R_{⟨n,q⟩}$

Let’s define the following ciphertext-to-plaintext multiplication operation:

$\mathrm{\Lambda }\cdot C=(\mathrm{\Lambda }\cdot A_0,\mathrm{\Lambda }\cdot A_1,...\mathrm{\Lambda }\cdot A_{k-1},\mathrm{\Lambda }\cdot B)$

We assume that we always do polynomial-to-polynomial multiplications efficiently in $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$ by using the NTT technique (§A-16). Then, the following is true:

This means that multiplying a plaintext (polynomial) by a ciphertext (polynomial) and decrypting it gives the same result as multiplying the two original plaintext polynomials.

If we decrypt ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot \mathrm{\Lambda }\cdot M)$ by using $S$, then we get the plaintext $\mathrm{\Lambda }\cdot M$. Meanwhile, $A_1^{\prime },A_2^{\prime },...A_{k-1}^{\prime },E^{\prime }$ 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 $C$’s noise has increased from $E$ to $E^{\prime }=\mathrm{\Lambda }\cdot E$. This means that if we continue multiplication computations without decrypting the ciphertext to blow away the noise $E^{\prime }$, 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^{\prime }$ won’t be blown away during decryption, ending up corrupting the plaintext $M$. Therefore, if the constant $\mathrm{\Lambda }$ is big, it is recommended to use gadget decomposition (§A-6.4), which we will explain in the next subsection.