C-3.1 Gadget Decomposition for Noise Suppression

In ciphertext-to-plaintext multiplication $\mathrm{\Lambda }\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(M)$, the noise $E$ grows to $E^{\prime }=\mathrm{\Lambda }\cdot E$. To limit this noise growth, we introduce a technique based on decomposing $\mathrm{\Lambda }$ (§A-6.1) and a GLev encryption (§B-5.1) of $M$ as follows:

$\mathrm{\Lambda }={\mathrm{\Lambda }}_1{\displaystyle \frac{q}{{\beta }^1}}+{\mathrm{\Lambda }}_2{\displaystyle \frac{q}{{\beta }^2}}+\cdots +{\mathrm{\Lambda }}_l{\displaystyle \frac{q}{{\beta }^l}}\to {\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(\mathrm{\Lambda })=({\mathrm{\Lambda }}_1,{\mathrm{\Lambda }}_2,\cdots ,{\mathrm{\Lambda }}_l)$

${\mathsf{\text{𝖦𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(\mathrm{\Delta }M)=\{{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }M{\displaystyle \frac{q}{{\beta }^1}}\right),{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }M{\displaystyle \frac{q}{{\beta }^2}}\right),\cdots {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }M{\displaystyle \frac{q}{{\beta }^l}}\right)\}$

We will encrypt the plaintext $M$ as ${\mathsf{\text{𝖦𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(\mathrm{\Delta }M)$ instead of ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)$, and compute $\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}({\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(\mathrm{\Lambda })\cdot {\mathsf{\text{𝖦𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(\mathrm{\Delta }M)$ instead of $\mathrm{\Lambda }\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)$. Notice that the results of both computations are the same as follows:

${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(\mathrm{\Lambda })\cdot {\mathsf{\text{𝖦𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(\mathrm{\Delta }M)$

$=({\mathrm{\Lambda }}_1,{\mathrm{\Lambda }}_2,\cdots ,{\mathrm{\Lambda }}_l)\cdot \left({\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{\beta }}\mathrm{\Delta }M\right),{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^2}}\mathrm{\Delta }M\right),\cdots ,{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^l}}\mathrm{\Delta }M\right)\right)$

$={\mathrm{\Lambda }}_1\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{\beta }}\mathrm{\Delta }M\right)+{\mathrm{\Lambda }}_2\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^2}}\mathrm{\Delta }M\right)+\cdots +{\mathrm{\Lambda }}_l\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^l}}\mathrm{\Delta }M\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_1\cdot {\displaystyle \frac{q}{\beta }}M\right)+{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_2\cdot {\displaystyle \frac{q}{{\beta }^2}}M\right)+\cdots +{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_l\cdot {\displaystyle \frac{q}{{\beta }^l}}M\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_1\cdot {\displaystyle \frac{q}{\beta }}\mathrm{\Delta }M+{\mathrm{\Lambda }}_2\cdot {\displaystyle \frac{q}{{\beta }^2}}\mathrm{\Delta }M+\cdots +{\mathrm{\Lambda }}_l\cdot {\displaystyle \frac{q}{{\beta }^l}}\mathrm{\Delta }M\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\left({\mathrm{\Lambda }}_1\cdot {\displaystyle \frac{q}{\beta }}+{\mathrm{\Lambda }}_2\cdot {\displaystyle \frac{q}{{\beta }^2}}+\cdots +{\mathrm{\Lambda }}_l\cdot {\displaystyle \frac{q}{{\beta }^l}}\right)\cdot \mathrm{\Delta }M\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Lambda }\cdot \mathrm{\Delta }M\right)$

$=\mathrm{\Lambda }\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)$

While the computation results are the same, as we decompose $\mathrm{\Lambda }$ into smaller plaintext polynomials ${\mathrm{\Lambda }}_1,{\mathrm{\Lambda }}_2,\cdots ,{\mathrm{\Lambda }}_l$, the generated noise by each of $l$ plaintext-to-ciphertext multiplications becomes smaller. Given the noise of each GLWE ciphertext in the GLev ciphertext is $E_i$, the final noise of the ciphertext-to-plaintext multiplication is $\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\mathrm{\Lambda }}_i\cdot E_i$, which is much smaller than $\mathrm{\Lambda }\cdot E$ (because the coefficients of each decomposed polynomial ${\mathrm{\Lambda }}_i$ are significantly smaller than those of $\mathrm{\Lambda }$). This is visually depicted in Figure 11.

However, we cannot use this decomposition technique to the resulting ciphertext again, because the output of this algorithm is a GLWE ciphertext and converting it into a GLev ciphertext without decrypting it costs much noise and computation time (as we need to multiply the GLWE ciphertext by ${\displaystyle \frac{q}{\beta }},{\displaystyle \frac{q}{{\beta }^2}},\cdots ,{\displaystyle \frac{q}{{\beta }^l}})$.

As a more efficient technique to re-initialize the noise $E$, we will describe TFHE’s noise bootstrapping technique in §D-1.8.