b02-lwe.tex

\textbf{- Reference:} 
\href{https://www.zama.ai/post/tfhe-deep-dive-part-1}{TFHE Deep Dive: Part I - Ciphertext types}~\cite{tfhe-1}



$ $




\subsection{Setup}
Let $[0, t-1)$ be the plaintext range, and $[0, q-1)$ the ciphertext range, where $t < q$ ($t$ is much smaller than $q$). Randomly pick a vector $\vec{s}$ of length $k$ comprising $k$ ternary numbers sampled from $\{-1, 0, 1\}$ as a secret key (denoted as $\vec{s} \xleftarrow{\$} \{-1, 0, 1\}^k$). Let $\Delta = \dfrac{q}{t}$, the scaling factor of plaintext.

\subsection{Encryption}
\label{subsec:lwe-enc}

\begin{enumerate}
\item Suppose we have a plaintext $m \in \mathbb{Z}_t$ to encrypt. \item Randomly pick a vector $\vec{a} \in \mathbb{Z}_q^k$ (of length $k$) as a one-time random public mask (denoted as $\vec{a} \xleftarrow{\$} \mathbb{Z}_q^k$).
\item Randomly pick a small one-time noise $e \in \mathbb{Z}_q$ sampled from the Gaussian distribution $\chi_\sigma$ (denoted as $e \xleftarrow{\chi_\sigma} \mathbb{Z}_q$). 
\item Scale $m$ by $\Delta$, which is to compute $\Delta \cdot m$. This converts $m \in \mathbb{Z}_t$ into $\Delta \cdot m \in \mathbb{Z}_q$.
\item Compute $b = \vec{a} \cdot \vec{s} + \Delta \cdot m + e \in \mathbb{Z}_q$. 
\end{enumerate}

$ $

The LWE encryption formula is summarized as follows:

$ $

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:lwe-enc}} LWE Encryption}}]
\textbf{\underline{Initial Setup}:} $\Delta = \dfrac{q}{t}$, $\vec{s} \xleftarrow{\$} \{-1, 0, 1\}^k$, where $t$ divides $q$

$ $

$ $

\textbf{\underline{Encryption Input}:} $m \in \mathbb{Z}_t$, $\vec{a} \xleftarrow{\$} \mathbb{Z}_q^k$, $e \xleftarrow{\chi_\sigma} \mathbb{Z}_q$

$ $

%\textbf{Encryption}

\begin{enumerate}
\item Scale up $m \longrightarrow \Delta \cdot m \text{ } \in \mathbb{Z}_q$

\item Compute $b = \vec{a} \cdot \vec{s} + \Delta  m + e \pmod q$
\item $\textsf{LWE}_{\vec{s},\sigma}(\Delta  m + e) = (\vec{a}, b) \text{ } \in \mathbb{Z}_q^{k + 1}$ 
\end{enumerate}

\end{tcolorbox}

\subsection{Decryption}
\label{subsec:lwe-dec} 

\begin{enumerate}
\item Given the ciphertext $(\vec{a}, b)$ where $b = \vec{a} \cdot \vec{s} + \Delta \cdot m + e \in \mathbb{Z}_q$, compute $b - \vec{a} \cdot \vec{s}$, which gives the same value as $\Delta \cdot m + e \in \mathbb{Z}_q$. 
\item Round $\Delta \cdot m + e \in \mathbb{Z}_q$ to the nearest multiple of $\Delta$ (i.e., round it as a base $\Delta$ number), which is denoted as $\lceil \Delta \cdot m + e \rfloor_{\Delta}$. This rounding operation successfully eliminates $e$ and gives $\Delta m$, provided $e$ is small enough to be $e < \dfrac{\Delta}{2}$. If $e \geq \dfrac{\Delta}{2}$, then some of the higher bits of the noise $e$ will overlap with the plaintext $m$, won't be blown away, and will corrupt some lower bits of the plaintext $m$.
\item Compute $\dfrac{\Delta m} {\Delta}$, which is equivalent to right-shifting $\lceil \Delta \cdot m + e \rfloor_{\Delta}$ by $\text{log}_2 \Delta$ bits. (Here we assume $\Delta$ is a power of 2; if $\Delta$ is not a power of 2, scaling up or down $m$ by $\Delta$ is equivalent to multiplying or dividing the value by $\Delta$.) 
\end{enumerate}

$ $

The LWE decryption formula is summarized as follows:

$ $

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:lwe-dec}} LWE Decryption}}]

\textbf{\underline{Decryption Input}:} $\textsf{ct} = (\vec{a}, b) \text{ } \in \mathbb{Z}_q^{k+1}$

$ $

%\textbf{Decryption}
\begin{enumerate}
\item $\textsf{LWE}^{-1}_{S,\sigma}(\textsf{ct}) = b - \vec{a}\cdot \vec{s} = \Delta  m + e \pmod q$

\item Scale down $\Bigg\lceil\dfrac{ \Delta  m + e } {\Delta}\Bigg\rfloor \bmod t = m \text{ } \in \mathbb{Z}_t$
\end{enumerate}

For correct decryption, the noise $e$ should be $e < \dfrac{\Delta}{2}$.

\end{tcolorbox}

During decryption, the secret key owner can subtract $\vec{a} \cdot \vec{s}$ from $b$ because he can directly compute $\vec{a} \cdot \vec{s}$ by using his secret key $\vec{s}$. 

The reason we scaled the plaintext $m$ by $\Delta$ is: (i) to left-shift $m$ by $\text{log}_2\Delta$ bits and separate it from the noise $e$ in the lower bits during encryption, whereas $e$ is essential to make it hard for the attacker to guess $m$ or $\vec{s}$; and (ii) to eliminate $e$ in the lower bits by right-shifting it by $\text{log}_2\Delta$ bits without compromising $m$ in the higher bits during decryption. The process of right-shifting (i.e., scaling) the plaintext $m$ by $\text{log}_2\Delta$ bits, followed by adding the noise $e$, is illustrated in \autoref{fig:scaling}.

\subsubsection{In the Case of $t$ not Dividing $q$}
\label{subsubsec:lwe-noise-bound}

In Summary~\ref*{subsec:lwe-enc} (\autoref{subsec:lwe-enc}), we assumed that $t$ divides $q$. In this case, there is no upper or lower limit on the size of plaintext $m$: its value is allowed to wrap around modulo $t$ indefinitely, yet the decryption works correctly. This is because any $m$ value greater than $t$ will be correctly modulo-reduced by $t$ when we perform modulo reduction by $q$ during decryption.

On the other hand, suppose that $t$ does not divide $q$. In such a case, we set the scaling factor as $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$. 
Then, provided $q \gg t$, the decryption works correctly even if $m$ is a large value that wraps around $t$. We will show why this is so. 

In this subsection's analysis, we choose $t$ to be an odd (prime) number, which is the general FHE practice for computational efficiency reasons (see \autoref{subsubsec:poly-vector-transformation-modulus}). 
We assume the use of the centered residue system, where the plaintext domain is $\left[-\dfrac{t-1}{2}, \dfrac{t-1}{2}\right]$ and the ciphertext domain is $\left[-\dfrac{q}{2}, \dfrac{q}{2} - 1\right]$.
We denote plaintext $m \bmod t$ as $m = m' + vt$, where $m' \in \mathbb{Z}_t$, and $v$ is an integer that represents the $t$-overflow portions of $m$. We set the plaintext scaling factor as $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$. Then, the noise-added and $\Delta$-scaled plaintext can be expressed as follows:

$\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m + e $

$= \left\lfloor\dfrac{q}{t}\right\rfloor\cdot m' + \left\lfloor\dfrac{q}{t}\right\rfloor\cdot vt + e$   \textcolor{red}{ $\rhd$ applying $m = m' + vt$}

$= \left\lfloor\dfrac{q}{t}\right\rfloor\cdot m' + \dfrac{q}{t}\cdot vt - \left(\dfrac{q}{t} - \left\lfloor\dfrac{q}{t}\right\rfloor\right)\cdot vt + e$  

$= \left\lfloor\dfrac{q}{t}\right\rfloor\cdot m' + qv - \left(\dfrac{q}{t} - \left\lfloor\dfrac{q}{t}\right\rfloor\right)\cdot vt + e$

$= \left\lfloor\dfrac{q}{t}\right\rfloor\cdot m' + qv - \epsilon \cdot vt + e$ \textcolor{red}{ $\rhd$ where $\epsilon = \dfrac{q}{t} - \left\lfloor\dfrac{q}{t}\right\rfloor$, a fractional value between $[0, 1)$}

$ $

Remember that the LWE decryption relation: $\dfrac{b - \vec{a}\cdot \vec{s} \bmod q}{\Delta} \bmod t = \dfrac{\Delta m + e \bmod q}{\Delta} \bmod t$. Therefore, from the above expression, we can decrypt the message by computing as follows:



$\left\lceil\dfrac{1}{\Delta} \cdot \left(b - \vec{a}\cdot\vec{s} \bmod q\right)\right\rfloor \bmod t$

$= \left\lceil\dfrac{1}{\Delta} \cdot \left(\Delta m + e \bmod q\right)\right\rfloor \bmod t$

$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor \cdot (m' + vt) + e \bmod q\right)\right\rfloor \bmod t$

$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor \cdot m' + \left\lfloor\dfrac{q}{t}\right\rfloor\cdot vt + e \bmod q\right)\right\rfloor \bmod t$

$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor \cdot m' + \left(\dfrac{q}{t} - \epsilon \right)\cdot vt + e \bmod q\right)\right\rfloor \bmod t$

$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor \cdot m' + vq - \epsilon vt + e \bmod q\right)\right\rfloor \bmod t$


$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e \bmod q \right)\right\rfloor \bmod t$ 

$ $

In order for the decryption to work, we ideally want to eliminate the inner modulo $q$ reduction. That is, assuming the centered residue system $\left[-\dfrac{q}{2}, \dfrac{q}{2}-1\right]$, we want $-\dfrac{q}{2} \leq \left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e < \dfrac{q}{2}$, or more strictly, $\left|\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e\right| < \dfrac{q}{2}$.

$ $

To ensure these conditions hold, we will make a special assumption: $|-\epsilon vt + e| < \dfrac{\Delta}{2}$. Applying this assumption to the expression above, we can derive the following relation:

$\left|\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e\right| $

$ \leq \left|\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'\right| + \left|- \epsilon vt + e\right|$

$ \leq \left|\left\lfloor\dfrac{q}{t}\right\rfloor\cdot \dfrac{t-1}{2}\right| + \left|- \epsilon vt + e\right|$ \textcolor{red}{ $\rhd$ we assume $t$ is an odd prime, as that's the general FHE practice}

$ \leq \left|\dfrac{q}{t}\cdot \dfrac{t-1}{2}\right| + \left|- \epsilon vt + e\right|$

$ = \dfrac{q}{2} - \dfrac{q}{2t} + \left|- \epsilon vt + e\right|$

$ < \dfrac{q}{2} - \dfrac{q}{2t} + \dfrac{\Delta}{2}$ \textcolor{red}{ $\rhd$ applying our special assumption $|-\epsilon vt + e| < \dfrac{\Delta}{2}$}

$ = \dfrac{q}{2} + \dfrac{1}{2}\cdot \left(\Delta - \dfrac{q}{t}\right)$

$< \dfrac{q}{2}$ \textcolor{red}{ $\rhd$ since $\Delta < \dfrac{q}{t}$}


$ $

Therefore, if we assume $|-\epsilon vt + e| < \dfrac{\Delta}{2}$, then $\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e \bmod q$ can be simplified to $\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e$. We continue with the following derivation: 


$\left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e \bmod q \right)\right\rfloor \bmod t$ 

$= \left\lceil\dfrac{1}{\left\lfloor\frac{q}{t}\right\rfloor} \cdot \left(\left\lfloor\dfrac{q}{t}\right\rfloor\cdot m'  - \epsilon vt + e \right)\right\rfloor \bmod t$ 



$= \left\lceil m' + \dfrac{-\epsilon  vt + e  }{\lfloor\frac{q}{t}\rfloor} \right\rfloor \bmod t$ 

$= m' + \left\lceil \dfrac{-\epsilon vt + e }{\lfloor\frac{q}{t}\rfloor} \right\rfloor \bmod t$ \textcolor{red}{ $\rhd$ since $\lceil m' \rfloor = m'$}

$= m' \bmod t$  \textcolor{red}{ $\rhd$ applying special assumption $|-\epsilon vt + e| < \dfrac{\Delta}{2} = \dfrac{\lfloor\frac{q}{t}\rfloor}{2}$}

To summarize, if we set the plaintext's scaling factor as $\Delta=\left\lfloor\dfrac{q}{t}\right\rfloor$ and $t$ is an odd (prime) number, the decryption works correctly as long as the following  error-bounding condition holds: $|-\epsilon vt + e| < \dfrac{\Delta}{2} = \dfrac{\lfloor\frac{q}{t}\rfloor}{2}$. This condition (i.e.,  decryption) breaks if: (1) the noise $e$ is too large relative to $q$; (2) the plaintext modulus $t$ is too large relative to $q$; or (3) the plaintext value wraps around $t$ too many times (i.e., $v$ is too large). A general solution to ensure all these error bound conditions is to set the ciphertext modulus $q$ to be sufficiently large. To put it differently, if $q \gg t$ and $q \gg e$, then the error bound holds. 

We can generalize the formula for the plaintext's scaling factor in Summary~\ref*{subsec:lwe-enc} (in \autoref{subsec:lwe-enc}) as $\left\lfloor\dfrac{q}{t}\right\rfloor$, where $t$ is an odd (prime) number. 


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsubsec:lwe-noise-bound}} Noise Budget for an Odd Plaintext Modulus $\bm{t}$}}]


Given the plaintext's scaling factor $\Delta=\left\lfloor\dfrac{q}{t}\right\rfloor$ and $t$ is an odd (prime) number, the LWE decryption works correctly as long as the error-bounding condition holds: 

$|-\epsilon vt + e| < \dfrac{\Delta}{2}$

$ $

, where $\epsilon = \dfrac{q}{t} - \left\lfloor\dfrac{q}{t}\right\rfloor$ is a fractional value between $[0, 1)$, and $v$ accounts for the $t$-overflows of the plaintext $m$.

\end{tcolorbox}