c03-glwe-mult-plain.tex

\textbf{- Reference:} 
\href{https://www.zama.ai/post/tfhe-deep-dive-part-2}{TFHE Deep Dive - Part II - Encodings and linear leveled operations}~\cite{tfhe-2}

$ $

Suppose we have a GLWE ciphertext \textsf{ct}:

$\textsf{ct} = \textsf{GLWE}_{S, \sigma}(\Delta M + E) = ( A_0, A_1, \ldots, A_{k-1}, B) \in \mathcal{R}_{\langle n,q \rangle}^{k + 1}$

$ $

\noindent and a new plaintext polynomial $\Lambda$ as follows: 

$\Lambda = \sum\limits_{i=0}^{n-1}(\Lambda_i \cdot X_i) \in \mathcal{R}_{\langle n, q \rangle}$

$ $

\noindent Let's define the following ciphertext-to-plaintext multiplication operation:

$\Lambda \cdot \textsf{ct} = (\Lambda \cdot A_0, \Lambda \cdot A_1, \ldots, \Lambda \cdot A_{k-1}, \Lambda \cdot B)$

$ $

\noindent We assume that we always do polynomial-to-polynomial multiplications efficiently in $O(n \log n)$ by using the NTT technique (\autoref{sec:ntt}). Then, the following is true: 

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{sec:glwe-mult-plain}} GLWE Ciphertext-to-Plaintext Multiplication}}]
$\Lambda \cdot \textsf{GLWE}_{S, \sigma}(\Delta M + E)$

$= \Lambda \cdot (\{A_i^{\langle 1 \rangle}\}_{i=0}^{k-1}, \text{ } B^{\langle 1 \rangle})$

$= (\{\Lambda\cdot A_i^{\langle 1 \rangle}\}_{i=0}^{k-1}, \text{ } \Lambda \cdot B^{\langle 1 \rangle})$

$= \textsf{GLWE}_{S, \sigma}(\Delta (M \cdot \Lambda) + \Lambda\cdot E )$
\end{tcolorbox}

This means that multiplying a plaintext polynomial $\Lambda$ by a GLWE ciphertext that encrypts $M$  and decrypting it yields $M \cdot \Lambda$.  

$ $

%\noindent \textbf{\underline{Proof}}
\begin{myproof}
\begin{enumerate}
\item Define the following notations: \\
$A_0' = \Lambda \cdot A_0$ \\
$A_1' = \Lambda \cdot A_1$ \\
$\vdots$ \\
$A_{k-1}' = \Lambda \cdot A_{k-1}$ \\
$E' = \Lambda \cdot E$ \\
$B' = \Lambda \cdot B$ \\
\item Derive the following: \\
$B' = \Lambda \cdot B$ \\
$= \Lambda \cdot (\sum\limits_{i=0}^{k-1}{(A_i \cdot S_i)} + \Delta \cdot M + E)$ 
$= \sum\limits_{i=0}^{k-1}{(\Lambda \cdot A_i \cdot S_i)} + \Delta \cdot \Lambda \cdot M + \Lambda \cdot E$   \\ \textcolor{red}{ $\rhd$ by the distributive property of a polynomial ring} \\
$= \sum\limits_{i=0}^{k-1}{((\Lambda \cdot A_i) \cdot S_i)} + \Delta \cdot (\Lambda \cdot M) + (\Lambda \cdot E)$  \\
$= \sum\limits_{i=0}^{k-1}{(A_i' \cdot S_i)} + \Delta \cdot (\Lambda \cdot M) + (E')$ \\
\item Since $B' = \sum\limits_{i=0}^{k-1}{(A_i' \cdot S_i)} + \Delta \cdot (\Lambda \cdot M) + (E')$, 

$(A_0', A_1', \ldots, A_{k-1}'
, B')$ form the ciphertext $\textsf{GLWE}_{S, \sigma}(\Delta \cdot \Lambda \cdot M)$.
\item Thus, \\
$\Lambda \cdot \textsf{GLWE}_{S, \sigma}(\Delta M + E)$ \\
$ = (\Lambda \cdot A_0, \text { } \Lambda \cdot A_1, \ldots, \Lambda \cdot A_{k-1}, \text { } \Lambda \cdot B)$ \\
$ = ( \{A'_{i}\}_{i=0}^{k-1}, \text { } \Lambda \cdot B)$ \\
$= \textsf{GLWE}_{S, \sigma}(\Delta (M \cdot \Lambda) + \Lambda \cdot E)$

%\begin{flushright}
%\qedsymbol{} 
%\end{flushright}
\end{enumerate}
\end{myproof}

If we decrypt $\textsf{GLWE}_{S, \sigma}(\Delta \cdot \Lambda \cdot M + \Lambda \cdot E)$ by using $S$, then we get the plaintext $\Lambda \cdot M$. Meanwhile, $A_0', A_1', \ldots, 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 \textsf{ct}'s noise has increased from $E$ to $E' = \Lambda \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 $\Lambda$ is big, it is recommended to use gadget decomposition (\autoref{subsec:gadget-decomposition}), which we will explain in the next subsection. 

\subsection{Gadget Decomposition for Noise Suppression}
\label{subsubsec:gadget-decomposition-noise-suppression}

In the ciphertext-to-plaintext multiplication $\Lambda \cdot \textsf{GLWE}_{S, \sigma}(\Delta M)$, the noise $E$ grows to $E' = \Lambda \cdot E$. To limit this noise growth, we introduce a technique based on decomposing $\Lambda$ (\autoref{subsec:number-decomp}) and a GLev encryption (\autoref{subsec:glev-enc}) of $M$ as follows:


$\Lambda = \Lambda_1 \dfrac{q}{\beta^1} + \Lambda_2 \dfrac{q}{\beta^2} + \cdots + \Lambda_l \dfrac{q}{\beta^l} \longrightarrow \textsf{Decomp}^{\beta, l}(\Lambda) = (\Lambda_1, \Lambda_2, \cdots, \Lambda_l)$

$ $

$\textsf{GLev}_{S, \sigma}^{\beta, l}(\Delta M) = \Bigg\{ \textsf{GLWE}_{S, \sigma}\left(\Delta M \dfrac{q}{\beta^1} + E_1\right), \textsf{GLWE}_{S, \sigma}\left(\Delta M \dfrac{q}{\beta^2} + E_2\right), \cdots \textsf{GLWE}_{S, \sigma}\left(\Delta M \dfrac{q}{\beta^l} + E_l\right) \Bigg\}$

$ $


We will encrypt the plaintext $M$ as $\textsf{GLev}_{S, \sigma}^{\beta, l}(\Delta M)$ instead of $\textsf{GLWE}_{S, \sigma}(\Delta M)$, and compute $\textsf{Decomp}^{\beta, l}(\Lambda) \cdot \textsf{GLev}_{S, \sigma}^{\beta, l}(\Delta M)$ instead of $\Lambda \cdot \textsf{GLWE}_{S, \sigma}(\Delta M)$. Notice that the results of both computations are the same as follows:

$\textsf{Decomp}^{\beta, l}(\Lambda) \cdot \textsf{GLev}_{S, \sigma}^{\beta, l}(\Delta M)$

$= (\Lambda_1, \Lambda_2, \cdots, \Lambda_l) \cdot \left (\textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta} \Delta M + E_1\right), \text{ } \textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta^2} \Delta M + E_2\right), \text{ } \cdots, \text{ } \textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta^l} \Delta M + E_l\right) \right )$

$= \Lambda_1\cdot\textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta} \Delta M + E_1\right) +  \Lambda_2\cdot\textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta^2} \Delta M + E_2\right) + \cdots + \Lambda_l\cdot\textsf{GLWE}_{S, \sigma}\left(\dfrac{q}{\beta^l} \Delta M + E_l\right)$

$= \textsf{GLWE}_{S, \sigma}\left(\Lambda_1\cdot\dfrac{q}{\beta}\Delta M + \Lambda_1 E_1\right) +\textsf{GLWE}_{S, \sigma}\left(\Lambda_2\cdot\dfrac{q}{\beta^2}\Delta M + \Lambda_2 E_2\right)+ \cdots + \textsf{GLWE}_{S, \sigma}\left(\Lambda_l\cdot\dfrac{q}{\beta^l}\Delta M + \Lambda_l E_l\right)$

$= \textsf{GLWE}_{S, \sigma}\left(\Lambda_1\cdot\dfrac{q}{\beta} \Delta M + \Lambda_2\cdot\dfrac{q}{\beta^2} \Delta M + \cdots + \Lambda_l\cdot\dfrac{q}{\beta^l} \Delta M\right)$

$= \textsf{GLWE}_{S, \sigma}\left(\left(\Lambda_1\cdot\dfrac{q}{\beta} + \Lambda_2\cdot\dfrac{q}{\beta^2} + \cdots + \Lambda_l\cdot\dfrac{q}{\beta^l}\right)\cdot \Delta M  + E_{\textit{all}} \right)$ \textcolor{red}{ $\rhd$ where $E_{\textit{all}} = \sum\limits_{i=1}^l \Lambda_iE_i$}

$= \textsf{GLWE}_{S, \sigma}\left(\Lambda \cdot \Delta M + E_{\textit{all}}\right)$ \textcolor{red}{ $\rhd$ whose decryption is $\Lambda\cdot M$}

$ $

While the decrypted results are the same, as we decompose $\Lambda$ into smaller plaintext polynomials $\Lambda_1, \Lambda_2, \cdots, \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_{\textit{all}} = \sum\limits_{i=1}^{l}\Lambda_i\cdot E_i$, which is much smaller than $\Lambda \cdot E$, because 
the coefficients of each decomposed polynomial $\Lambda_i$ are significantly smaller than those of $\Lambda$ (i.e., 
$\|\Lambda_i\|_\infty \le \beta/2$, whereas $\|\Lambda\|_\infty$ can be as large as $q/2$). This is visually depicted in~\autoref{fig:decomp2}.

\begin{figure}[h!]
    \centering
  \includegraphics[width=0.8\linewidth]{figures/decomp2.pdf}
  \caption{Noise reduction in ciphertext-to-plaintext multiplication by gadget decomposition.}
  \label{fig:decomp2}
\end{figure}

\subsubsection{Discussion}
\label{subsubsec:glwe-mult-plain-discuss}


Nevertheless, the decomposition technique is still very useful: for GLWE key-switching (\autoref{sec:glwe-key-switching}), we will show how to key-switch by combining decomposed mask polynomials $\textsf{Decomp}^{\beta,l}(A_i)$
with a precomputed key-switching key
$\textsf{KSK}_i=\textsf{GLev}^{\beta,l}_{S',\sigma}(S_i)$,
so gadget decomposition can be repeatedly leveraged across key-switching calls even though each individual application outputs a standard GLWE ciphertext.

Meanwhile, for the technique to repeatedly re-initialize the noise $E$ of regular ciphertexts, we will describe TFHE's noise bootstrapping technique in \autoref{subsec:tfhe-noise-bootstrapping}.