C-3.1 Gadget Decomposition for Noise Suppression

In the ciphertext-to-plaintext multiplication $\mathrm{\Lambda }\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }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}}+E_1\right),{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }M{\displaystyle \frac{q}{{\beta }^2}}+E_2\right),\cdots {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left(\mathrm{\Delta }M{\displaystyle \frac{q}{{\beta }^l}}+E_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{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\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+E_1\right),{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^2}}\mathrm{\Delta }M+E_2\right),\cdots ,{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\displaystyle \frac{q}{{\beta }^l}}\mathrm{\Delta }M+E_l\right)\right)$

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

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_1\cdot {\displaystyle \frac{q}{\beta }}\mathrm{\Delta }M+{\mathrm{\Lambda }}_1{E}_1\right)+{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_2\cdot {\displaystyle \frac{q}{{\beta }^2}}\mathrm{\Delta }M+{\mathrm{\Lambda }}_2{E}_2\right)+\cdots +{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S,\sigma }\left({\mathrm{\Lambda }}_l\cdot {\displaystyle \frac{q}{{\beta }^l}}\mathrm{\Delta }M+{\mathrm{\Lambda }}_l{E}_l\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+E_{\mathit{\text{𝑎𝑙𝑙}}}\right)$ $▹$ where $E_{\mathit{\text{𝑎𝑙𝑙}}}=\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\mathrm{\Lambda }}_i{E}_i$

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

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

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 noise generated 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 $E_{\mathit{\text{𝑎𝑙𝑙}}}=\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 }$ (i.e., $\parallel {\mathrm{\Lambda }}_i{\parallel }_{\infty }\le \beta ∕2$, whereas $\parallel \mathrm{\Lambda }{\parallel }_{\infty }$ can be as large as $q∕2$). 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.