d04-bgv.tex

Similar to BFV, the BGV scheme is designed for homomorphic addition and multiplication of integers. Unlike CKKS, BGV guarantees exact encryption and decryption. From this view, BGV is similar to BFV. However, the major difference between these two schemes is that BFV stores the plaintext value in the MSBs (most significant bits) and the noise in the low-digit area (least significant bits), while BGV stores them the other way around: the plaintext value in the low-digit area and the noise in the MSBs. Technically, while BFV scales the plaintext polynomial by $\Delta$, BGV scales the noise polynomial by $\Delta$. Therefore, these two schemes use slightly different strategies to store and manage the plaintext and noise within a ciphertext. 

BGV internally uses almost the same strategy as BFV for plaintext encoding, ciphertext-to-plaintext addition, ciphertext-to-ciphertext addition, ciphertext-to-plaintext multiplication, and input vector rotation. On the other hand, BGV's encryption and decryption are slightly different from BFV's scheme, because its scaling target is not the plaintext, but the noise. Also, unlike BFV where ciphertext-to-ciphertext multiplication has no limit on the number, BGV's ciphertext-to-ciphertext multiplication is leveled, switching the modulus to a lower level like CKKS, and thus it is limited. Furthermore, BGV's modulus switch and bootstrapping are partially different from BFV's. 



\begin{tcolorbox}[
    title = \textbf{Required Background},    % box title
    colback = white,    % light background; tweak to taste
    colframe = black,  % frame colour
    boxrule = 0.8pt,     % line thickness
    left = 1mm, right = 1mm, top = 1mm, bottom = 1mm % inner padding
]

\begin{itemize}
\item \autoref{sec:modulo}: \nameref{sec:modulo}
\item \autoref{sec:group}: \nameref{sec:group}
\item \autoref{sec:field}: \nameref{sec:field}
\item \autoref{sec:order}: \nameref{sec:order}
\item \autoref{sec:polynomial-ring}: \nameref{sec:polynomial-ring}
\item \autoref{sec:decomp}: \nameref{sec:decomp}
\item \autoref{sec:roots}: \nameref{sec:roots}
\item \autoref{sec:cyclotomic}: \nameref{sec:cyclotomic}
\item \autoref{sec:cyclotomic-polynomial-integer-ring}: \nameref{sec:cyclotomic-polynomial-integer-ring}
\item \autoref{sec:matrix}: \nameref{sec:matrix}
\item \autoref{sec:euler}: \nameref{sec:euler}
\item \autoref{sec:modulus-rescaling}: \nameref{sec:modulus-rescaling}
\item \autoref{sec:chinese-remainder}: \nameref{sec:chinese-remainder}
\item \autoref{sec:polynomial-interpolation}: \nameref{sec:polynomial-interpolation}
\item \autoref{sec:ntt}: \nameref{sec:ntt}
\item \autoref{sec:lattice}: \nameref{sec:lattice}
\item \autoref{sec:rlwe}: \nameref{sec:rlwe}
\item \autoref{sec:glwe}: \nameref{sec:glwe}
\item \autoref{sec:glwe-add-cipher}: \nameref{sec:glwe-add-cipher}
\item \autoref{sec:glwe-add-plain}: \nameref{sec:glwe-add-plain}
\item \autoref{sec:glwe-mult-plain}: \nameref{sec:glwe-mult-plain}
\item \autoref{subsec:modulus-switch-rlwe}: \nameref{subsec:modulus-switch-rlwe}
\item \autoref{sec:glwe-key-switching}: \nameref{sec:glwe-key-switching}
\item \autoref{sec:bfv}: \nameref{sec:bfv}
\item \autoref{sec:ckks}: \nameref{sec:ckks}
\end{itemize}
\end{tcolorbox}

\clearpage

\subsection{Encoding and Decoding}
\label{subsec:bgv-encoding-decoding}

BGV uses almost the same plaintext encoding scheme as BFV as described in Summary~\ref{subsubsec:bfv-encoding-summary} in \autoref{subsubsec:bfv-encoding-summary}, with the only difference that the scaling factor $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$ is not applied to the plaintext polynomial $M(X)$ like BFV does. Instead, BGV applies its own scaling factor $\Delta = t$ to the noise polynomial $E(X)$ whenever it encrypts a new ciphertext (will be explained in \autoref{subsec:bgv-enc-dec}). 

The following is BGV's encoding and decoding scheme. 

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-encoding-decoding}} BGV's Encoding and Decoding}}]



\textbf{\underline{Input}:} An $n$-slot integer modulo $t$ vector $\vec{v} = (v_0, v_1, \cdots, v_{n-1}) \in \mathbb{Z}_t^n$

$ $

\textbf{\underline{Encoding}:} 

 Convert $\vec{v} \in \mathbb{Z}_t^n$ into $\vec{m} \in \mathbb{Z}_t^n$ by applying the transformation $\vec{m} = \dfrac{\hathat W \cdot I_n^R \cdot \vec{v}}{n}$

, where $\hathat W$ is a basis of the $n$-dimensional vector space crafted as follows: 

{\footnotesize{$\hathat W = \begin{bmatrix}
1 & 1 & \cdots & 1 & 1 & 1 & \cdots & 1\\
(\omega^{J(\frac{n}{2} - 1)}) & (\omega^{J(\frac{n}{2} - 2)}) & \cdots & (\omega^{J(0)}) & (\omega^{J_*(\frac{n}{2} - 1)}) & (\omega^{J_*(\frac{n}{2} - 2)}) & \cdots & (\omega^{J_*(0)})\\
(\omega^{J(\frac{n}{2} - 1)})^2 & (\omega^{J(\frac{n}{2} - 2)})^2 & \cdots & (\omega^{J(0)})^2 & (\omega^{J_*(\frac{n}{2} - 1)})^2 & (\omega^{J_*(\frac{n}{2} - 2)})^2 & \cdots & (\omega^{J_*(0)})^2 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots & \vdots \\
(\omega^{J(\frac{n}{2} - 1)})^{n-1} & (\omega^{J(\frac{n}{2} - 2)})^{n-1} & \cdots & (\omega^{J(0)})^{n-1} & (\omega^{J_*(\frac{n}{2} - 1)})^{n-1} & (\omega^{J_*(\frac{n}{2} - 2)})^{n-1} & \vdots  & (\omega^{J_*(0)})^{n-1}
\end{bmatrix}$}}

$ $

, where $\omega$ is a primitive $2n$-th root of unity modulo $t$ (which implies $t \equiv 1 \bmod 2n$). This implies that $\omega = g^{\frac{t - 1}{2n}} \bmod t$ ($g$ is a generator of $\mathbb{Z}_t^{\times}$ (see \autoref{subsubsec:poly-vector-transformation-modulus}). The final output is $M = \sum\limits_{i=0}^{n-1} m_iX^i \text{ } \in \mathbb{Z}_t[X] / (X^n + 1)$, 
which we can also treat as 

$M = \sum\limits_{i=0}^{n-1} m_iX^i \text{ } \in \mathbb{Z}_q[X] / (X^n + 1)$ during encryption/decryption later, because the initial fresh coefficients $m_i$ are guaranteed to be smaller than any $q$ where $q = \{q_0, q_1, \cdots, q_L\}$.

$ $

\textbf{\underline{Decoding}:} For the plaintext polynomial $M = \sum\limits_{i=0}^{n-1} m_iX^i$, 
compute $\vec{v} = \hathat W^* \cdot \vec{m}$, where 

$\hathat{W}^* = \begin{bmatrix}
1 & (\omega^{J(0)}) & (\omega^{J(0)})^2 & \cdots & (\omega^{J(0)})^{n-1}\\
1 & (\omega^{J(1)}) & (\omega^{J(1)})^2 & \cdots & (\omega^{J(1)})^{n-1}\\
1 & (\omega^{J(2)}) & (\omega^{J(2)})^2 & \cdots & (\omega^{J(2)})^{n-1}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (\omega^{J(\frac{n}{2}-1)}) & (\omega^{J(\frac{n}{2}-1)})^2 & \cdots & (\omega^{J(\frac{n}{2}-1)})^{n-1}\\
1 & (\omega^{J_*(0)}) & (\omega^{J_*(0)})^2 & \cdots & (\omega^{J_*(0)})^{n-1}\\
1 & (\omega^{J_*(1)}) & (\omega^{J_*(1)})^2 & \cdots & (\omega^{J_*(1)})^{n-1}\\
1 & (\omega^{J_*(2)}) & (\omega^{J_*(2)})^2 & \cdots & (\omega^{J_*(2)})^{n-1}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (\omega^{J_*(\frac{n}{2}-1)}) & (\omega^{J_*(\frac{n}{2}-1)})^2 & \cdots & (\omega^{J_*(\frac{n}{2}-1)})^{n-1}\\
\end{bmatrix}$

\end{tcolorbox}


\subsection{Encryption and Decryption}
\label{subsec:bgv-enc-dec}

BGV's encryption and decryption scheme is very similar to BFV's scheme (Summary~\ref*{subsec:bfv-enc-dec} in \autoref{subsec:bfv-enc-dec}) with a small difference: while BFV scales the plaintext polynomial $M(X)$ by $\Delta$, BGV scales the noise polynomial $E(X)$ by $\Delta$. In BFV, each encoded plaintext polynomial $M(X)$ is scaled by $ \Delta = \left\lfloor \dfrac{q}{t} \right\rfloor$. This strategy effectively shifts each plaintext coefficient value to the most significant bits while keeping the noise in the least significant bits. On the other hand, BGV does not scale the plaintext polynomial $M(X)$, but instead it scales each new noise $E(X)$ by $\Delta = t$, making the noise $\Delta E(X)$, which is newly generated upon each new ciphertext creation. This different scaling strategy effectively shifts the noise (i.e., $e_i$) to the most significant bits by scaling it by $\Delta = t$ while keeping the plaintext value (i.e., $m_i$) $M(X)$'s each coefficient in the least significant bits. 

Also, in BGV, the ciphertext modulus $q$ is leveled like CKKS's one: $q \in \{q_0, q_1, \cdots, q_L\}$, where each $q_l = \prod\limits_{i=0}^l w_i$ (where each $w_i$ is a CRT modulus). 

BGV's encryption decryption process is described as follows:


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-enc-dec}} BGV Encryption and Decryption}}]

\textbf{\underline{Initial Setup}:} 

\begin{itemize}
\item The plaintext modulus $t = p$ (a prime)

\item The ciphertext modulus $q$ is leveled like in CKKS: $q \in \{q_0, q_1, \cdots, q_L\}$, where each $q_l = \prod\limits_{i=0}^l w_i$ (each $w_i$ is a CRT modulus), and each $q_l \equiv 1 \bmod t$ (will be explained in \autoref{subsec:bgv-modulus-switch})

\item The noise scaling factor $\Delta=t$ 
\item The secret key $S \xleftarrow{\$} \mathcal{R}_{\langle n, \textit{tern} \rangle}$. The coefficients of the polynomial $S$ ternary (i.e., $\{-1, 0, 1\}$).

\end{itemize}

\par\noindent\rule{\textwidth}{0.4pt}

\textbf{\underline{Encryption Input}:} $M \in \mathcal{R}_{\langle n, q \rangle}$, $A \xleftarrow{\$} \mathcal{R}_{\langle n, q \rangle}$, $E \xleftarrow{\chi_\sigma} \mathcal{R}_{\langle n, q \rangle}$


\begin{enumerate}
%\item Scale up $M \rightarrow \Delta M \text { } \in \mathcal{R}_{\langle n, q\rangle}$

\item Compute $B = -A \cdot S + M + \Delta E \text{ } \in \mathcal{R}_{\langle n,q \rangle}$

\item $\textsf{RLWE}_{S,\sigma}(M + \Delta E) = (A, B) \text{ } \in \mathcal{R}_{\langle n,q \rangle}^2$ 

\end{enumerate}

\par\noindent\rule{\textwidth}{0.4pt}

\textbf{\underline{Decryption Input}:} $\textsf{ct} = (A, B) \text{ } \in \mathcal{R}_{\langle n,q \rangle}^2$

\begin{enumerate}
\item $\textsf{RLWE}^{-1}_{S,\sigma}(\textsf{ct}) = B + A \cdot S  = M + \Delta E \pmod q$

\item Compute $M + \Delta E \bmod t$ to get $M$. \textcolor{red}{ $\rhd$ modulo reduction of $M + \Delta E$ by $t$}

\end{enumerate}

$ $

The final output is $M(X) \in \mathbb{Z}_t[X] / (X^n + 1)$.

$ $

\textbf{\underline{Conditions for Correct Decryption}:}

%\begin{enumerate}
%\item 
Each coefficient $\Delta e_i + m_i$ that contains the scaled noise and the plaintext should not overflow or underflow its ciphertext's any current moment's multiplicative level $l$'s ciphertext modulus $q_l$ (i.e., $\Delta e_i + m_i < q_l$, or $|\Delta e_i + m_i| < \frac{q_l}{2}$ in the signed modulo representation). 

%\end{enumerate}

\end{tcolorbox}

When restoring the plaintext at the end of the decryption process, while BFV shifts down the plaintext and the noise to the lower bit area (which effectively rounds off the noise), BGV computes $\text{ mod } p$, which effectively modulo-reduces the accumulated noise because every coefficient of $E$ is a multiple of $t$ (i.e., $\Delta$). Finally, only each coefficient of the plaintext polynomial $m_i$ remains in the low-digit area without any noise $e_i$. 



\subsection{Ciphertext-to-Ciphertext Addition}
\label{subsec:bgv-add-cipher}

BGV's ciphertext-to-ciphertext addition scheme is exactly the same as BFV's scheme (Summary~\ref*{subsec:bfv-add-cipher} in \autoref{subsec:bfv-add-cipher}). 


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-add-cipher}} BGV Ciphertext-to-Ciphertext Addition}}]
$\textsf{RLWE}_{S, \sigma}(M^{\langle 1 \rangle} + \Delta E^{\langle 1 \rangle} ) + \textsf{RLWE}_{S, \sigma}(M^{\langle 2 \rangle} + \Delta E^{\langle 2 \rangle}) $

$ = ( A^{\langle 1 \rangle}, \text{ } B^{\langle 1 \rangle}) + (A^{\langle 2 \rangle}, \text{ } B^{\langle 2 \rangle}) $

$ = ( A^{\langle 1 \rangle} + A^{\langle 2 \rangle}, \text{ } B^{\langle 1 \rangle} + B^{\langle 2 \rangle} ) $

$= \textsf{RLWE}_{S, \sigma}\bm((M^{\langle 1 \rangle} + M^{\langle 2 \rangle})  + \Delta E^{\langle 1 \rangle} + \Delta E^{\langle 2 \rangle} \bm)$
\end{tcolorbox}

\subsection{Ciphertext-to-Plaintext Addition}
\label{subsec:bgv-add-plain}

BGV's ciphertext-to-plaintext addition scheme is almost the same as BFV's scheme (Summary~\ref*{subsec:bfv-add-plain} in \autoref{subsec:bfv-add-plain}). However, one difference is that it's not the case that the plaintext polynomial $\Lambda(X)$ to be added is scaled up by $\Delta$, but it remains as $\Lambda(X)$.

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-add-plain}} BGV Ciphertext-to-Plaintext Addition}}]
$\textsf{RLWE}_{S, \sigma}(M + \Delta E) + \Lambda $

$=  (A, \text{ } B) + \Lambda$

$=  (A, \text{ } B + \Lambda)$

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


\subsection{Ciphertext-to-Plaintext Multiplication}
\label{subsec:bgv-mult-plain}




BGV's ciphertext-to-plaintext multiplication scheme is exactly the same as BFV's scheme (Summary~\ref*{subsec:bfv-mult-plain} in \autoref{subsec:bfv-mult-plain}). 


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

$= (A, \text{ } B) \cdot \Lambda$

$= (A \cdot \Lambda, \text{ }  B \cdot \Lambda )$

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

Notice that BGV's ciphertext-to-plaintext multiplication does not consume any multiplicative level. 

\subsection{\textsf{ModDrop}}
\label{subsec:bgv-moddrop}

BGV's \textsf{ModDrop} works similarly to that of CKKS's \textsf{ModDrop} (Summary~\ref*{subsec:ckks-moddrop} in \autoref{subsec:ckks-moddrop}). Remember that CKKS's ciphertext decryption relation is as follows:

$M + \Delta E = A \cdot S + B \bmod q_l$

$M + \Delta E = A \cdot S + B - K\cdot q_l$ \textcolor{red}{ $\rhd$ where $K\cdot q_l$ represents a modulo reduction by $q_l$}

BGV's \textsf{ModDrop} operation decreases its modulus from $q_l \rightarrow q_{l-1}$ is performed by updating the ciphertext $(A, B)$ to a new one: $\bm(A' = A \bmod q_{l-1}$, $B' = B \bmod q_{l-1})$. After the \textsf{ModDrop}, the ciphertext's modulus decreases from $q_l \rightarrow q_{l-1}$, yet its decryption relation still holds the same as follows:

$A' \cdot S + B' - K\cdot q_l $

$= (A \bmod q_{l-1}) \cdot S + (B \bmod q_{l-1}) - K\cdot q_l$

$= (A - K_A\cdot q_{l-1}) \cdot S + (B - K_B\cdot q_{l-1}) - K\cdot q_l$ 

$= A\cdot S + B - (K_A \cdot S + K_B + K\dfrac{q}{q_{l-1}})\cdot q_{l-1}$
\textcolor{red}{ $\rhd$ where $\dfrac{q}{q_{l-1}} = w_l$ (i.e., the $l$-th prime element of $q_L$)}

$= A\cdot S + B - K'\cdot q_{l-1}$ \textcolor{red}{ $\rhd$ where $K' = K_A\cdot S + K_B + K\dfrac{q}{q_{l-1}}$, $\dfrac{q}{q_{l-1}} = w_l$ }

$= A\cdot S + B \bmod q_{l-1}$

$= M + \Delta E$ \textcolor{red}{ $\rhd$ since $M + \Delta E < q_0 < q_{l-1}$}

$ $

As shown above, $(A', B') \bmod q_{l-1}$ decrypts to the same $M + \Delta E$, a plaintext with a scaled error. However, the noise budget (i.e., allowed threshold of the noise) decreases because the ciphertext modulus-to-noise ratio decreases. 

$ $

BGV's \textsf{ModDrop} is summarized as follows:



\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-moddrop}} BGV's \textsf{ModDrop}}}]

Given a BGV ciphertext with the $l$-th multiplicative level $\textsf{RLWE}_{S, \sigma}(M + \Delta E) = (A, B) \bmod q_l$, a \textsf{ModDrop} operation is as follows: 

$(A', B') \bmod q_{l-1} = (A \bmod q_{l-1}, B \bmod q_{l-1})$

$ $

After this, the ciphertext's multiplicative level decreases by 1, the noise's scaling factor $\Delta$ and the plaintext are unaffected, and the noise budget (i.e., allowed noise threshold) decreases. 

\end{tcolorbox}



\subsection{Modulus Switch}
\label{subsec:bgv-modulus-switch}

\noindent \textbf{- Reference 1:} 
\href{https://eprint.iacr.org/2020/1481}{Design and implementation of HElib: a homomorphic encryption library}~\cite{bgv-modswitch1}


\noindent \textbf{- Reference 2:} 
\href{https://eprint.iacr.org/2011/277.pdf}{Fully Homomorphic Encryption without Bootstrapping}~\cite{bgv-modswitch2}


\noindent \textbf{- Reference 3:} 
\href{https://eprint.iacr.org/2012/099.pdf}{Homomorphic Evaluation of the AES Circuit}~\cite{bgv-modswitch3}

Remember that the requirement of modulus switch is that while we change the ciphertext modulus from $q$ to $\hat q$, it should decrypt to the same plaintext $M$. BGV's modulus switch is similar to that of the RLWE modulus switch (\autoref{subsec:modulus-switch-rlwe}), but there is an additional requirement, because BGV applies the scaling factor $\Delta$ not to plaintext $M$, but to noise $E$. In the case of BFV or CKKS, their decryption process only needs to round off the noise in the low-digit area. However, in the case of BGV, the plaintext is in the low-digit area and its decryption process has to remove the noise in the higher-bit area by modulo-$t$ reduction (i.e., the plaintext modulus). More concretely, BGV's modulus switch from $(A, B) \bmod q_{l}$ $\rightarrow$  $(\hat{A}, \hat{B}) \bmod \hat{q}$ should satisfy the decryption relation such that $((\hat{A} \cdot S + \hat{B}) \bmod \hat{q}) \bmod t = M$. In BGV's modulus switch, $\hat{q}$ does not have to be one of the multiplicative levels of the ciphertext, and $\hat{q}$ only needs to satisfy the relationship: $\hat{q} < q_l$ and $\hat{q} \equiv 1 \bmod t$. BGV's modulus switch procedure is as follows:

$ $

\begin{enumerate}


\item The input ciphertext is $\textsf{ct} = (A, B) \bmod q_l$. We compute new polynomials $A'$ and $B'$ as follows:

$(A', B') = \left(\left\lceil\dfrac{\hat{q}}{q_l}\cdot A\right\rfloor, \left\lceil\dfrac{\hat{q}}{q_l}\cdot B\right\rfloor\right) \pmod{\hat{q}}$

$ $

And we compute the rounding error $\epsilon_A, \epsilon_B$ as follows: 

$\epsilon_A = \dfrac{\hat{q}}{q_l}\cdot A - A'$

$\epsilon_B = \dfrac{\hat{q}}{q_l}\cdot B - B'$


$ $

, which we rewrite as follows:

$\hat{q} A = q_{l} A' + q_{l}\epsilon_A = q_{l} A' + \epsilon'_A$ \textcolor{red}{ $\rhd$ we denote $\epsilon'_A = q_{l}\epsilon_A$, where $\epsilon'_A \in \mathbb{Z}_{q_l}$}

$\hat{q} B = q_{l} B' + q_{l}\epsilon_B = q_{l} B' + \epsilon'_B$ \textcolor{red}{ $\rhd$ we denote $\epsilon'_B = q_{l}\epsilon_B$, where $\epsilon'_B \in \mathbb{Z}_{q_l}$}

$ $

\item We compute new polynomials $H_A$ and $H_B$ as follows:

$H_A = q_l^{-1}\cdot\epsilon'_A \bmod t$

$H_B = q_l^{-1}\cdot\epsilon'_B \bmod t$

$ $

\item We propose the final mod-switched ciphertext $\hat{\textsf{ct}}$ as follows:

$\hat{\textsf{ct}} = (\hat{A}, \hat{B}) = (A' + H_A, \text{ } B' + H_B) \bmod \hat{q}$

$ $

Note that the computation result of $A' + H_A$ and $B' + H_B$ alone can exceed the range $\mathbb{Z}_{\hat{q}}$, because $A', B' \in \mathbb{Z}_{\hat{q}}$ and $H_A, H_B \in \mathbb{Z}_t$. Therefore, our goal is reduce $A' + H_A$ and $B' + H_B$ modulo $\hat{q}$  to derive $\hat{A} \in \mathbb{Z}_{\hat{q}}$ and $\hat{B} \in \mathbb{Z}_{\hat{q}}$. 

$ $

\item From now on, we will verify that $\hat{\textsf{ct}}$ is a valid ciphertext satisfying BGV's required decryption relation. First, we can derive the relationship among $\textsf{ct} = (A, B)$, $A' + H_A$, and $B' + H_B$ as follows:

$\hat{q}\cdot \textsf{ct} \bmod t $

$= (\hat{q}A, \hat{q}B) \bmod t$

$= (q_{l} A' + \epsilon'_A, \text{ } q_{l} B' + \epsilon'_B) \bmod t$ \textcolor{red}{ $\rhd$ applying step 1's result: $\hat{q} A = q_{l}A' + \epsilon'_A$, \text{ }  $\hat{q} B = q_{l}B' + \epsilon'_B$}

$ = (q_{l} A' + q_lH_A, \text{ } q_{l} B' + q_lH_B) \bmod t$ 
\textcolor{red}{ $\rhd$ applying step 2's result: $H_A = q_l^{-1}\cdot\epsilon'_A \bmod t$, \text{ } $H_B = q_l^{-1}\cdot\epsilon'_B \bmod t$}

$ $

$ = q_l\cdot(A' + H_A, \text{ } B' + H_B) \bmod t$

%$ = q_l \cdot \hat{\textsf{ct}} \bmod t$

$ $

So, $\hat{q}\cdot\textsf{ct} = q_l\cdot(A' + H_A, \text{ } B' + H_B) \bmod t$. But in BGV, $q_l \equiv q_2 \equiv \cdots \equiv \hat{q} \equiv \cdots q_L \equiv 1 \bmod t$. Thus, the following holds:

$A \equiv A' + H_A \bmod t$

$B \equiv B' + H_B \bmod t$




$ $

\item We can derive the decryption relation of $\hat{\textsf{ct}}$ from the decryption relation of $\textsf{ct}$ as follows:

$M = (A\cdot S + B \bmod q_l) \bmod t$ \textcolor{red}{ $\rhd$ The BGV decryption relation of $\textsf{ct} = (A, B) \bmod q_l$}

$= (A\cdot S + B - K\cdot q_l) \bmod t$ \textcolor{red}{ $\rhd$ where $K\cdot q_l$ represents the modulo-$q_l$ reduction}

$= ((A' + H_A)\cdot S + B' + H_B - K\cdot q_{l}) \bmod t$ \textcolor{red}{ $\rhd$ applying step 4's result: $A \equiv A' + H_A \bmod t$, \text{ } $B \equiv B' + H_B \bmod t$}

$= ((A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q}) \bmod t$ \textcolor{red}{ $\rhd$ since in BGV, $q_0\equiv q_1\equiv \cdots q_L \equiv 1 \bmod t$, and we chose $\hat{q}$ such that $\hat{q} \equiv 1 \bmod t$}

$ $

\item Now, if we can prove that $(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q} = (A' + H_A)\cdot S + B' + H_B \bmod \hat{q}$ (i.e., $K\cdot\hat{q}$ reduces $(A' + H_A)\cdot S + B' + H_B$ modulo $\hat{q}$), then this sufficiently leads to the following conclusion: 

$(\hat{A}\cdot S + \hat{B} \bmod \hat{q}) \bmod t$

$= ((A' + H_A)\cdot S + B' + H_B \bmod \hat{q}) \bmod t$

$= M$ \textcolor{red}{ $\rhd$ i.e., $(\hat{A}, \hat{B}) = (A' + H_A, B' + H_B) \bmod \hat{q}$ is a valid ciphertext that decrypts to $M$}

$ $
\begin{comment}
\item The following is also true: 

$(A' + H_A)\cdot S + B' + H_B \bmod \hat{q}$

$ = |A' + H_A|_{\hat{q}}\cdot S + |B' + H_B|_{\hat{q}} \bmod \hat{q}$ 

\textcolor{red}{ $\rhd$ where $|A' + H_A|_{\hat{q}} = A' + H_A \bmod \hat{q}$, \text{ } $|B' + H_B|_{\hat{q}} = B' + H_B \bmod \hat{q}$} 

$ $

$ = \hat{A}\cdot S + \hat{B} \bmod \hat{q}$ \textcolor{red}{ $\rhd$ applying step 3: $\hat{A} = A' + H_A \bmod \hat{q}$, \text{ } $\hat{B} = B' + H_B \bmod \hat{q}$}

$ $

Therefore, proving $(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q} = (A' + H_A)\cdot S + B' + H_B \bmod \hat{q}$ is equivalent to proving $(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q} = \hat{A}\cdot S + \hat{B} \bmod \hat{q}$. 

$ $
\end{comment}


\item We will prove that $(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q} = (A' + H_A)\cdot S + B' + H_B \bmod \hat{q}$ as follows: 

$(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q}$ 


$ = (\dfrac{\hat{q}}{q_{l}}\cdot A - \dfrac{\epsilon'_A}{q_{l}} + H_A)\cdot S + (\dfrac{\hat{q}}{q_{l}}\cdot B - \dfrac{\epsilon'_B}{q_{l}} + H_B) - K\cdot \hat{q}$ 

\textcolor{red}{ $\rhd$ applying step 1's result: $A' = \dfrac{\hat{q}}{q_{l}}\cdot A - \dfrac{\epsilon'_A}{q_{l}}, \text{ } B' = \dfrac{\hat{q}}{q_{l}}\cdot B - \dfrac{\epsilon'_B}{q_{l}}$}

$ $

$ $

$ = \left(\dfrac{\hat{q}}{q_{l}}\cdot A\cdot S + \dfrac{\hat{q}}{q_{l}}\cdot B  - K\cdot \hat{q}\right) + H_A\cdot S + H_B - \dfrac{\epsilon'_A}{q_{l}}\cdot S - \dfrac{\epsilon'_B}{q_{l}}$ \textcolor{red}{ $\rhd$ rearranging the terms}

$ = \dfrac{\hat{q}}{q_{l}}\cdot(A\cdot S + B  - K\cdot q_{l}) + H_A\cdot S + H_B - \dfrac{\epsilon'_A}{q_{l}}\cdot S - \dfrac{\epsilon'_B}{q_{l}}$ \textcolor{red}{ $\rhd$ taking out the common factor $\dfrac{\hat{q}}{q_{l}}$}

$ = \dfrac{\hat{q}}{q_{l}}\cdot(A\cdot S + B \bmod q_l) + H_A\cdot S + H_B - \dfrac{\epsilon'_A\cdot S + \epsilon'_B}{q_{l}}$ \textcolor{red}{ $\rhd$ since $A\cdot S + B - K\cdot q_{l} = A\cdot S + B \bmod q_l$}

$ $

For successful decryption, every coefficient of the resulting polynomial of the above expression has to be within the range $\mathbb{Z}_{\hat{q}}$ (which means that $K\cdot\hat{q}$ has successfully reduced $(A' + H_A)\cdot S + B' + H_B$ modulo $\hat{q}$). The first term $\dfrac{\hat{q}}{q_{l}}\cdot(A\cdot S + B \bmod q_l)$ can be viewed as the original ciphertext \textsf{ct}'s noise (with the plaintext message) scaled down by $\dfrac{\hat{q}}{q_l}$, which is guaranteed to be within the $\mathbb{Z}_{\hat{q}}$ range. The coefficients of the second term $H_A \cdot S$ are also small, because $H_A \in \mathbb{Z}_t^n$ and $S \in \{-1, 0, 1\}^n$. The coefficients of the third term $H_B$ are also small, because $H_B \in \mathbb{Z}_t^n$. The coefficients of the last term $- \dfrac{\epsilon'_A\cdot S + \epsilon'_B}{q_{l}}$ are also small, because $\dfrac{\epsilon'_A}{q_l}$ and $\dfrac{\epsilon'_B}{q_l}$ are $\in \mathbb{Z}_{\frac{q_l}{\hat{q}}}$. 

$ $

Therefore, $(A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q} = (A' + H_A)\cdot S + B' + H_B \bmod \hat{q}$ (provided the above error thresholds hold). 

$ $

\item Finally, we combine the results of step 6 and 7 as follows: 

$\bm((\hat{A}\cdot S + \hat{B}) \bmod \hat{q} \bm) \bmod t$

$= \bm((A' + H_A)\cdot S + B' + H_B \bmod \hat{q}\bm) \bmod t$ \textcolor{red}{ $\rhd$ since $\hat{A} \equiv A' + H_A \bmod \hat{q}$, and $\hat{B} \equiv B' + H_B \bmod \hat{q}$}

$ = ((A' + H_A)\cdot S + B' + H_B - K\cdot \hat{q}) \bmod t$ \textcolor{red}{ $\rhd$ by applying step 7}

$ = M$ \textcolor{red}{ $\rhd$ by applying step 5}

$ $

Hence, decrypting $(\hat{A}, \hat{B}) \bmod \hat{q}$ outputs the message $M$.

\end{enumerate}

$ $

We summarize BGV's modulus switch as follows:



\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-modulus-switch}} BGV's Modulus Switch}}]

Suppose we have the current ciphertext modulus $q_l$ and new ciphertext modulus $\hat{q}$ where $q_l \equiv \hat{q} \equiv 1 \bmod t$ and $\hat{q} < q_l$. Therefore, $\hat{q}$ may or may not be one of the ciphertext moduli comprising a BGV ciphertext's multiplicative level moduli $q_0, q_1, \cdots, q_L$.

$ $

BGV's modulus switch from $q_l \rightarrow \hat{q}$ is equivalent to updating $(A, B) \bmod q_l$ to $(\hat A, \hat B) \bmod \hat{q}$ as follows:


$(A', B') = \left(\left\lceil\dfrac{\hat{q}}{q_l}\cdot A\right\rfloor, \left\lceil\dfrac{\hat{q}}{q_l}\cdot B\right\rfloor\right) \in \mathcal{R}_{\langle n, \hat{q} \rangle}^2$

$ $

$\epsilon'_A = \hat{q}\cdot A - q_l\cdot A'$ \textcolor{red}{ $\rhd$ where $\epsilon'_A \in \mathbb{Z}_{q_l}$}

$\epsilon'_B = \hat{q}\cdot B - q_l\cdot B'$ \textcolor{red}{ $\rhd$ where $\epsilon'_B \in \mathbb{Z}_{q_l}$}


$ $

$H_A = q_l^{-1}\cdot\epsilon'_A \bmod t$

$H_B = q_l^{-1}\cdot\epsilon'_B \bmod t$

$ $

$\hat{\textsf{ct}} = (\hat{A}, \hat{B}) = (A' + H_A, B' + H_B) \bmod \hat{q}$

$ $

BGV's modulus switch is used for ciphertext-to-ciphertext multiplication (will be covered in \autoref{subsec:bgv-mult-cipher}). Meanwhile, After BGV's modulus switch (i.e., the noise scaling factor), $\Delta = t$ stays the same as before. The secret key $S$ also stays the same as before. The noise gets scaled down roughly by $\dfrac{\hat{q}}{q_l}$, but this does not decrease the noise-to-ciphertext modulus ratio. The noise-to-ciphertext modulus ratio can be reduced by modulus bootstrapping (will be covered in \autoref{subsec:bgv-bootstrapping}). 

\end{tcolorbox}



\subsubsection{Difference between Modulus Switch and \textsf{ModDrop}}
\label{subsubsec:bgv-moddrop-vs-modswitch}

In the case of CKKS (\autoref{subsubsec:ckks-mult-cipher-rescale}), the difference between modulus switch and \textsf{ModDrop} is that the former scales down the plaintext's scaling factor by $\dfrac{q_l}{q_{l-1}} \approx \dfrac{1}{\Delta}$, whereas \textsf{ModDrop} does not affect the plaintext's scaling factor. 

Similarly, in the case of BGV, modulus switch (rescaling) and \textsf{ModDrop} from $q_l \rightarrow q_{l-1}$ both lower a BGV ciphertext's modulus from $q_l \rightarrow q_{l-1}$. However, the key difference is that rescaling also decreases the noise's scaling factor by $\dfrac{q_l}{q_{l-1}} \approx \dfrac{1}{\Delta}$, whereas \textsf{ModDrop} keeps the noise's scaling factor the same as it is. Therefore, rescaling is used only during ciphertext-to-ciphertext multiplication (to be explained in \autoref{subsec:bgv-mult-cipher}) when scaling down the noise's scaling factor in the intermediate ciphertext from $\Delta^2 \rightarrow \Delta$. Meanwhile, \textsf{ModDrop} is used to reduce the modulo computation time during an application's routine when it becomes certain that the ciphertext will not undergo any additional ciphertext-to-ciphertext multiplication (i.e., no need to further decrease the ciphertext's modulus). 

The main difference in modulus switch between CKKS and BGV is that the former decreases the plaintext's scaling factor by approximately $\dfrac{1}{\Delta}$, whereas the latter decreases the noise's scaling factor by approximately $\dfrac{1}{\Delta}$. 

\para{Source Code:} Examples of BGV modulus switch can be executed by running \href{https://github.com/fhetextbook/fhe-textbook/blob/main/source%20code/bgv.py}{\underline{this Python script}}. 


\subsection{Ciphertext-to-Ciphertext Multiplication}
\label{subsec:bgv-mult-cipher}

\noindent \textbf{- Reference:} 
\href{https://www.inferati.com/blog/fhe-schemes-bgv}{Introduction to the BGV encryption scheme}

Since BGV uses a leveled ciphertext modulus chain like CKKS, BGV's ciphertext-to-ciphertext multiplication scheme is exactly the same as CKKS's scheme (Summary~\ref*{subsec:ckks-mult-cipher} in \autoref{subsec:ckks-mult-cipher}), except for the rescaling step which uses BGV's modulus switch (\autoref{subsec:bgv-modulus-switch}). 

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-mult-cipher}} BGV Ciphertext-to-Ciphertext Multiplication}}]

Suppose we have the following two RLWE ciphertexts:

$\textsf{RLWE}_{S, \sigma}(M^{\langle 1 \rangle} + \Delta E^{\langle 1 \rangle}) = (A^{\langle 1 \rangle}, B^{\langle 1 \rangle})$, \text{ } where $B^{\langle 1 \rangle} = -A^{\langle 1 \rangle} \cdot S +  M^{\langle 1 \rangle} + \Delta E^{\langle 1 \rangle}$

$\textsf{RLWE}_{S, \sigma}(M^{\langle 2 \rangle} + \Delta E^{\langle 2 \rangle}) = (A^{\langle 2 \rangle}, B^{\langle 2 \rangle})$, \text{ } where $B^{\langle 2 \rangle} = -A^{\langle 2 \rangle} \cdot S +  M^{\langle 2 \rangle} + \Delta E^{\langle 2 \rangle}$

$ $

Multiplication between these two ciphertexts is performed as follows:

$ $

\begin{enumerate}
\item \textbf{\underline{Basic Multiplication}}

Compute the following:

$ $

$D_0 = B^{\langle 1 \rangle}\cdot B^{\langle 2 \rangle}$

$D_1 = A^{\langle 1 \rangle}\cdot B^{\langle 2 \rangle} + A^{\langle 2 \rangle}\cdot B^{\langle 1 \rangle}$

$D_2 = A^{\langle 1 \rangle} \cdot A^{\langle 2 \rangle}$

$ $

The decryption relation satisfies: $M^{\langle 1 \rangle}M^{\langle 2 \rangle} + \Delta\cdot (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + \Delta^2E^{\langle 1 \rangle}E^{\langle 2 \rangle}$

$ = \underbrace{B^{\langle 1 \rangle}\cdot B^{\langle 2 \rangle}}_{D_0}  + \underbrace{(B^{\langle 2 \rangle}\cdot A^{\langle 1 \rangle} + B^{\langle 1 \rangle}\cdot A^{\langle 2 \rangle})}_{D_1} \cdot S + \underbrace{(A^{\langle 1 \rangle} \cdot A^{\langle 2 \rangle})}_{D_2} \cdot \underbrace{S \cdot S}_{S^2}$

$= D_0 + D_1\cdot S + D_2 \cdot S^2$

$ $

\item \textbf{\underline{Relinearization}} 

$\textsf{RLWE}_{S, \sigma}\bm(M^{\langle 1 \rangle}M^{\langle 2 \rangle} + \Delta\cdot (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + \Delta^2E^{\langle 1 \rangle}E^{\langle 2 \rangle}\bm) $

$= \textsf{RLWE}_{S, \sigma}\bm{(}\text{ }D_0 + D_1\cdot S + D_2\cdot S^2\text{ }\bm{)}$

$  \approx C_\alpha + C_\beta, \text{ where } \text{ } C_\alpha = (D_1, D_0), \text{ }\text{ }\text{ } C_\beta = \bm{\langle}  \text{ } \textsf{Decomp}^{\beta, l}(D_2), \textsf{RLev}_{S, \sigma}^{\beta, l}(S^2)  \text{ } \bm{\rangle}$ 

$ $

\item \textbf{\underline{(Optional) Rescaling}}

To suppress the noise component scaled by $\Delta^2$ and return it to a factor of $\Delta$, switch the ciphertext's modulo from $q \rightarrow \hat q$ by updating $(A, B)$ to $(\hat A, \hat B)$ according to BGV's modulus switch explained in Summary~\ref*{subsec:bgv-modulus-switch} (\autoref{subsec:bgv-modulus-switch}).

$ $

After the above update of $(A, B)$ to $(\hat A, \hat B)$, the noise scaling factor $\Delta = t$ and the plaintext $M$ stay the same, as we proved in \autoref{subsec:bgv-modulus-switch} that $((\hat A \cdot S + \hat B) \bmod \hat q) \bmod t = M$.

$ $



\end{enumerate}

\para{Swapping the Order of \textsf{Relinearization} and \textsf{Rescaling}: } The order of relinearization and rescaling is interchangeable. Running rescaling before relinearization reduces the size of the ciphertext modulus, and therefore the subsequent relinearization can be executed faster. 

\end{tcolorbox}

\para{Details of the Optional Rescaling:} Before rescaling, the contents of the ciphertext are $M^{\langle 1 \rangle}M^{\langle 2 \rangle} + \Delta\cdot (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + \Delta^2E^{\langle 1 \rangle}E^{\langle 2 \rangle} + \epsilon$, where $\epsilon$ is a relinearization error. Therefore, after each ciphertext-to-ciphertext multiplication, the noise's scaling factor will become squared as $\Delta^2, \Delta^4, \Delta^8, \cdots$. To reduce such exponential noise growth rate, we can optionally rescale down the ciphertext by $w_l = \dfrac{q_l}{q_{l-1}} > \Delta$ at the end of each relinearization at multiplicative level $l$, which is the noise's growth rate (effectively keeping the noise scaling factor as $\Delta$). After rescaling, the ciphertext gets scaled down by $w_l$ and then added by a new noise $\epsilon_2$. Before the rescaling, the noise grew roughly by the factor of $\Delta = t$ (as the largest noise term is $\Delta^2 E^{\langle 1 \rangle} E^{\langle 2 \rangle}$), but the rescaling process reduces this growth rate by the factor of $w_l$ and then introduces a new constant noise $\epsilon_2$. Therefore, if $w_l$ is sufficiently bigger than $\Delta = t$, the resulting noise will decrease compared to both $\Delta E^{\langle 1 \rangle}$ and $\Delta E^{\langle 2 \rangle}$. Due to this reason, when we design the modulus chain of BGV, we require each $w_l$ to be sufficiently bigger than $\Delta = t$ to effectively reduce the noise growth rate upon each ciphertext-to-ciphertext multiplication (while ensuring the property that its reduction modulo $t$ gives the plaintext $M$ as explained in \autoref{subsec:bgv-modulus-switch}). Meanwhile, the constant noise term $\epsilon_2$ gets newly added upon each rescaling, but this term becomes part of the rescaled ciphertext, which will be later reduced by the factor of $w_{l-1}$ in the future rescaling. Therefore, BGV's rescaling upon ciphertext-to-ciphertext multiplication effectively suppresses the noise growth. 

On the other hand, the above design strategy of noise reduction is inapplicable to CKKS, because in CKKS, we use the scaling factor $\Delta$ to scale the message $M$ (not the noise $E$), and thus CKKS requires each $w_l \approx \Delta$ in order to preserve the plaintext's scaling factor $\Delta$ as the same value across ciphertext-to-ciphertext multiplications. Because of this difference in design, CKKS inevitably increases the noise after each ciphertext-to-ciphertext multiplication. 


\subsection{Homomorphic Key Switching}
\label{subsec:bgv-key-switching}

BGV's homomorphic key switching scheme changes an RLWE ciphertext's secret key from $S$ to $S'$. This scheme is exactly the same as BFV's key switching scheme (Summary~\ref*{subsec:bfv-key-switching} in \autoref{subsec:bfv-key-switching}).

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-key-switching}} BGV's Key Switching}}]
$\textsf{RLWE}_{S',\sigma}(M + \Delta E) = (0, B) + \bm{\langle} \textsf{Decomp}^{\beta, l}(A), \text{ } \textsf{RLev}_{S', \sigma}^{\beta, l}(S) \bm{\rangle}$
\end{tcolorbox}



\subsection{Homomorphic Rotation of Input Vector Slots}
\label{subsec:bgv-rotation}


BGV's homomorphic rotation scheme of input vector slots is exactly the same as BFV's rotation scheme (Summary~\ref*{subsec:bfv-rotation} in \autoref{subsec:bfv-rotation}). 


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bgv-rotation}} BGV's Homomorphic Rotation of Input Vector Slots}}]


Suppose we have a BGV ciphertext and a key-switching key as follows:

\[
\textsf{RLWE}_{S, \sigma}(M + \Delta E) = (A, B), \quad \textsf{RLev}_{S, \sigma}^{\beta, l}(S(X^{J(h)}))
\]

Then, the procedure of rotating the first-half elements of the ciphertext's original input vector $\vec{v}$ by $h$ positions to the left (in a wrapping manner among them) and the second-half elements of $\vec{v}$ by $h$ positions to the left (in a wrapping manner among them) is as follows: 

\begin{enumerate}
\item Update $A(X)$, $B(X)$ to $A(X^{J(h)})$, $B(X^{J(h)})$. 
\item Perform the following key switching (refer to \autoref{subsec:bfv-key-switching}) from $S(X^{J(h)})$ to $S(X)$:

$\textsf{RLWE}_{S(X),\sigma}\bm{(} M(X^{J(h)}) + \Delta E(X^{J(h)})\bm{)} $

$= \bm{(} 0, B(X^{J(h)}) \bm{)} \text{ } + \text{ } \bm{\langle}  \textsf{Decomp}^{\beta, l}\bm{(}A(X^{J(h)})\bm{)}, \text{ } \textsf{RLev}_{S(X), \sigma}^{\beta, l}\bm{(}S(X^{J(h)})\bm{)} \bm{\rangle}$
\end{enumerate}


\end{tcolorbox}




\subsection{Modulus Bootstrapping}
\label{subsec:bgv-bootstrapping}

\noindent \textbf{- Reference:} 
\href{https://eprint.iacr.org/2022/1363.pdf}{Bootstrapping for BGV and BFV Revisited}~\cite{cryptoeprint:2022/1363}

BGV's bootstrapping shares some common aspects with both BFV and CKKS's bootstrapping. The goal of BGV's bootstrapping is the same as that of CKKS, but the internal technique is closer to that of BFV. Like CKKS, BGV's bootstrapping resets the depleted ciphertext modulus from $q_l \rightarrow q_L$ (strictly speaking, from $q_l \rightarrow q_{l'}$ such that $l < l' < L$ because the bootstrapping operations between step 2$\sim$6 have consumed multiplicative levels). This modulus transition effectively not only resets the multiplicative level but also reduces the noise-to-ciphertext modulus ratio. To achieve this goal, one might think that BGV's bootstrapping can take the same \textsf{ModRaise} approach used by CKKS's bootstrapping. However, this is not a directly applicable solution because CKKS uses the sine approximation technique to eliminate the $q_0$-multiple overflows after the mod-raise. On the other hand, BGV is an exact encryption scheme that does not allow the approximation of plaintext values. Therefore, BGV uses BFV's digit extraction approach to eliminate its modulus overflows. To use digit extraction, as in the case of BFV, BGV also has to modify the plaintext modulus to a specially prepared one, $p^\varepsilon$. To configure both the plaintext modulus and the ciphertext modulus to the desired values (i.e., $p^\varepsilon$ and $q_L$), BGV employs the homomorphic decryption technique, as BFV does.  


The technical details of BGV's bootstrapping are as follows. 

$ $

Suppose that we have an RLWE ciphertext $(A, B)  = \textsf{RLWE}_{S, \sigma}(M + \Delta E) \bmod q_l$, where $A\cdot S + B = M + \Delta E$, \text{ } $\Delta = t = p$ (a prime), and $q_l$ is the ciphertext modulus of the current multiplicative level. 

$ $

\begin{enumerate}

\item \textbf{\underline{Modulus Switch} from \boldmath$q_l \rightarrow \hat{q}$:} BFV's bootstrapping initially switches the ciphertext modulus from $q \rightarrow p^{\varepsilon-1}$ where $q \gg p^\varepsilon > t = p$. On the other hand, BGV's bootstrapping switches the ciphertext modulus to $\hat{q}$ that is a special modulus satisfying the relation: $\hat{q} \equiv 1 \bmod p^\varepsilon$ and $\hat{q} > p^\varepsilon$ (where $p^\varepsilon$ will be explained in the next step). In order for a modulus switch from $q_l \rightarrow \hat{q}$ (i.e., the special modulus) to be possible, the prime factor(s) comprising $\hat{q}$ have to be congruent with $q_{0}, \ldots, q_L \bmod t$, so that we can do a modulus switch from $q_l\cdot \hat{q} \rightarrow \hat{q}$ (based on the technique learned in \autoref{subsec:bgv-modulus-switch}). Eventually, this step's modulus switch transforms the ciphertext $(A, B) \bmod q_l$ to $(\hat{A}, \hat{B}) \bmod \hat{q}$, during which the plaintext modulus (i.e., noise's scaling factor) stays the same. 

$ $

\item \textbf{\underline{Ciphertext Coefficient Multiplication by \boldmath$p^{\varepsilon-1}$}:} 
The constant $p^{\varepsilon-1}$ is multiplied to each coefficient of the ciphertext polynomials, updating the ciphertext to $p^{\varepsilon-1} \cdot (\hat{A}, \hat{B}) = (A', B') \bmod \hat{q}$, where $A' = p^{\varepsilon-1}\hat{A}$ and $B' = p^{\varepsilon-1}\hat{B}$. This operation updates the original decryption relation $\hat{A}\cdot S + \hat{B} = M + p E + K\hat{q}$ to $A'\cdot S + B' = p^{\varepsilon-1} M + p^\varepsilon E + K'\hat{q}$ (where $||K'||_{\infty} \leq n + 1$). Notice that the plaintext modulus (i.e., noise's scaling factor) has been changed from $p \rightarrow p^\varepsilon$. When choosing $\varepsilon$, BGV enforces the following additional constraint: $\hat{q} > p^\varepsilon$ and $\hat{q}  \equiv 1 \bmod p^\varepsilon$.

$ $

\item \textbf{\underline{\textsf{ModRaise}}:} We mod-raise $(\hat{A}, \hat{B}) \bmod \hat{q}$ to $(\hat{A}, \hat{B}) \bmod q_L$, where $\hat{q} \ll q_L$. The mod-raised ciphertext's decryption relation is as follows:

$\hat{A}\cdot S + \hat{B} = p^{\varepsilon-1}M + p^\varepsilon E + K'\hat{q} \bmod q_L$

$ $

Note that $K'\hat{q}$ is the $\hat{q}$-multiple overflow and does not get reduced modulo $q_L$, because $K'\hat{q} \ll q_L$. We saw the same situation in the CKKS bootstrapping's \textsf{ModRaise} (\autoref{subsubsec:ckks-bootstrapping-high-level}) which resets the ciphertext modulus from $q_0 \rightarrow q_L$ at the cost of incurring a $Kq_0$ overflow, which is to be removed by \textsf{EvalExp}'s homomorphic (approximate) sine graph evaluation (\autoref{subsubsec:ckks-bootstrapping-evalexp-details}). Likewise, BGV's mod-raised ciphertext $(\hat{A}, \hat{B}) \bmod q_L$ is $\textsf{RLWE}_{S, \sigma}(p^{\varepsilon-1}M + p^\varepsilon E + K'\hat{q}) \bmod q_L$, an encryption of $p^{\varepsilon-1}M + p^\varepsilon E + K'\hat{q}$. In the later step, we will use digit extraction to homomorphically eliminate $K'\hat{q}$ like we did in BFV's bootstrapping. The reason BGV's bootstrapping uses digit extraction instead of approximated sine evaluation is that BGV is an exact encryption scheme like BFV (not an approximate scheme like CKKS). 

$ $

\item \textbf{\textsf{\underline{CoeffToSlot}}:} This step works the same way as CKKS and BFV's \textsf{CoeffToSlot} step: move the coefficients of the polynomial $p^{\varepsilon-1} M + p^\varepsilon E + \hat{q}K'$ to the input vector slots of a new ciphertext. We denote polynomial $Z = p^{\varepsilon-1} M + p^\varepsilon E + \hat{q}K'$, and each $i$-th coefficient of $Z$ as $z_i$. For the \textsf{CoeffToSlot} step, we homomorphically compute $Z \cdot n^{-1} \cdot \hathat W \cdot I_n^R$. Then, each input vector slot of the resulting ciphertext ends up storing each $z_i$ of the polynomial $Z$. 

$ $

\item \textbf{\underline{Digit Extraction}:} At this point, each input vector slot contains each coefficient of $p^{\varepsilon-1} M + p^\varepsilon E + \hat{q}K'$, which is $p^{\varepsilon-1} m_i + p^\varepsilon e_i + \hat{q}k'_i$. Recall that we designed the lowest multiplicative level's ciphertext modulus $\hat{q}$ and the homomorphic multiplication factor $p^\varepsilon$ such that $\hat{q} \equiv 1 \bmod p^\varepsilon$, or $\hat{q} = k^{\langle \hat{q} \rangle } \cdot p^\varepsilon + 1$ for some positive integer $k^{\langle \hat{q} \rangle }$. Therefore, the following holds: 

$p^{\varepsilon-1} m_i + p^\varepsilon e_i + \hat{q}k'_i$

$ = p^{\varepsilon-1} m_i + p^\varepsilon e_i + k'_i\cdot(k^{\langle \hat{q} \rangle } \cdot p^\varepsilon + 1) $  \textcolor{red}{ $\rhd$ applying $\hat{q} = k^{\langle \hat{q} \rangle } \cdot p^\varepsilon + 1$}

$ = p^{\varepsilon-1} m_i + k'_i + p^\varepsilon  \cdot (e_i + k'_i\cdot k^{\langle \hat{q} \rangle }) $ \textcolor{red}{ $\rhd$ rearranging the terms}

$ = p^{\varepsilon-1} m_i + k'_i + p^\varepsilon \cdot k_i^{\langle \hat{q} + \varepsilon \rangle } $ \textcolor{red}{ $\rhd$ where $ k_i^{\langle \hat{q} + \varepsilon \rangle } = e_i + k'_i\cdot k^{\langle \hat{q} \rangle } $}

$ \equiv p^{\varepsilon-1} m_i + k'_i \pmod{p^\varepsilon}$

$ $

To eliminate $k'_i$ from the above (where $|k'_i| \leq n + 1$), we use the same digit extraction polynomial $G_{\varepsilon, v}$ as in the BFV bootstrapping (\autoref{subsubsec:bfv-bootstrapping-digit-extraction}) :

$z_i = d_0 + \left(\sum\limits_{j=\varepsilon'}^{\varepsilon-1} d_* p^j\right)$ \textcolor{red}{ $\rhd$ where $d_0 \in \mathbb{Z}_p$, \text{ } and $d_*$ can be any integer, \text{ } and $1 \leq \varepsilon' \leq \varepsilon$}

$F_{\varepsilon'}(z_i) \equiv d_0 \bmod p^{\varepsilon'+1}$

$G_{\varepsilon}(z_i) \equiv (z_i - \underbrace{F_{\varepsilon-1} \circ F_{\varepsilon-2} \circ \cdots \circ F_1}_{\varepsilon - 1 \text{ times}} (z_i)) \cdot |p^{-1}|_{q}$

$ $

We evaluate the digit extraction polynomial $G_{\varepsilon}$ for $\{\varepsilon, \varepsilon-1, \varepsilon-2, \cdots, 2\}$ recursively a total of $\varepsilon-1$ times. This operation finally zeros out and right-shifts the least significant (base-$p$) $\varepsilon-1$ digits of $z_i$ as follows:

$G_{2} \circ G_{3} \circ \cdots \circ G_{\varepsilon-1} \circ G_{\varepsilon} (z_i)$

$= m_i + k_i''p \bmod q_{l'}$

$ $

, where $k_i''p^\varepsilon$ is some multiple of $p^\varepsilon$ to account for the original $p^\varepsilon$-multiple overflow term plus additional $p^\varepsilon$-multiple overflows generated during the digit extraction. Note that the digit extraction step reduces the ciphertext modulus from $q_L \rightarrow q_{l'}$ (where $l'$ is an integer smaller than $L$), because the homomorphic evaluation of the polynomial $G_{\varepsilon}$ requires some ciphertext-to-ciphertext multiplications, which consume some multiplicative levels. The output of the digit extraction step is $m_i + k''_ip \bmod q_{l'}$ stored in each input vector slot. 

$ $

\para{\underline{Handling the Divisions by $p$}:} Unlike in BFV (\autoref{subsubsec:bfv-bootstrapping-digit-extraction}), we cannot use scaling factor re-interpretation because the scaling factor setup of BGV is different from that of BFV. In BGV's digit extraction, each round should explicitly homomorphically multiply the slot values by $|p^{-1}|_{q^{\langle i \rangle}}$, where $q^{\langle i \rangle}$ is the ciphertext modulus at the $i$-th round of digit extraction. Given $(A^{\langle g_1 \rangle}, B^{\langle g_1 \rangle}) \bmod q^{\langle 1 \rangle}$ is the ciphertext at the  1st round of digit extraction just before inverse-$p$ division, the actual division-by-$p$ is equivalent to performing the ciphertext-to-plaintext multiplication (\autoref{subsec:bfv-mult-plain}) as follows: 

$(A^{\langle g_1 \rangle}, B^{\langle g_1 \rangle}) \cdot \textsf{Encode}(p^{-1}) \bmod q^{\langle 1 \rangle}$

$= (A^{\langle g_1 \rangle}, B^{\langle g_1 \rangle}) \cdot p^{-1} \bmod q^{\langle 1 \rangle}$ \textcolor{red}{ $\rhd$ since $\textsf{Encode}(p^{-1}) = p^{-1} + 0X + 0X^2 + \cdots + 0X^{n-1}$ }

$= (p^{-1}A^{\langle g_1 \rangle}, p^{-1}B^{\langle g_1 \rangle}) \bmod q^{\langle 1 \rangle}$

$ $

Therefore, by multiplying the coefficients of two BGV ciphertext polynomials $A^{\langle g_1 \rangle}$ and $B^{\langle g_1 \rangle}$ by $|p^{-1}|_{q^{\langle 1 \rangle}}$, we obtain the following effect: 

$(|p^{-1}|_{q^{\langle 1 \rangle}} \cdot A^{\langle g_1 \rangle})\cdot S + (|p^{-1}|_{q^{\langle 1 \rangle}} \cdot B^{\langle g_1 \rangle}) \bmod q^{\langle 1 \rangle}$

$= |p^{-1}|_{q^{\langle 1 \rangle}} \cdot (p^{\varepsilon - 1}M + \left\lfloor{K'}\right\rfloor_p + K''p^{\varepsilon}) \bmod q^{\langle 1 \rangle}$


$= p^{\varepsilon - 2}M + \left\lfloor\dfrac{K'}{p}\right\rfloor + K''p^{\varepsilon-1} \bmod q^{\langle 1 \rangle} $

$ $

Verbally speaking, the above inverse-$p$ multiplication to all polynomial coefficients of $(A^{\langle g_1 \rangle}, B^{\langle g_2 \rangle})$ has the following two effects: (1) scales down the plaintext and the noise by $p$; and (2) reduces the modulus garbage term $K'$ to $\left\lfloor\dfrac{K'}{p}\right\rfloor$ (i.e., right-shift by 1 base-$p$ digit). 

$ $

BGV's digit extraction procedure is equivalent to recursively evaluating $G_{\varepsilon}$ with the input $z_i$ by decreasing $\varepsilon$ by 1 at each round (total $\varepsilon-1$ rounds) as follows:

\textbf{Input:} $p^{\varepsilon - 1}M + K' + K''p^{\varepsilon} \bmod \hat{q}$

\textbf{1st Round:} $G_{\varepsilon}(z_i) \xRightarrow{\text{effect}}  p^{\varepsilon - 2}M + \left\lfloor\dfrac{K'}{p}\right\rfloor + K''^{\langle 1 \rangle}p^{\varepsilon-1} \bmod q^{\langle 1 \rangle}$

\textbf{2nd Round:} $G_{\varepsilon-1} \circ G_{\varepsilon}(z_i) \xRightarrow{\text{effect}}  p^{\varepsilon - 3}M + \left\lfloor\dfrac{K'}{p^2}\right\rfloor + K''^{\langle 2 \rangle}p^{\varepsilon-2} \bmod q^{\langle 2 \rangle}$

\textbf{3rd Round:} $G_{\varepsilon-2} \circ G_{\varepsilon-1} \circ G_{\varepsilon}(z_i)  \xRightarrow{\text{effect}}  p^{\varepsilon - 4}M + \left\lfloor\dfrac{K'}{p^3}\right\rfloor + K''^{\langle 3 \rangle}p^{\varepsilon-3} \bmod q^{\langle 3 \rangle}$

$\vdots$

\textbf{$\bm{\varepsilon - 1}$-th Round:} $G_{2}\circ \cdots \circ G_{\varepsilon} (z_i) \xRightarrow{\text{effect}}  M + K''^{\langle \varepsilon - 1 \rangle}p \bmod q^{\langle \varepsilon - 1 \rangle}$

$ $

As shown above, the entire digit extraction procedure results in two effects on the values stored in the plaintext slots: (1) scales down the message $p^{\varepsilon - 1}M$ to $M$; and (2) zeros out the modulus garbage $K'$ (i.e., $\left\lfloor\dfrac{K'}{p^{\varepsilon - 1}}\right\rfloor = 0$). The reason why $K''$ gets updated to $K''^{\langle 1 \rangle}, K''^{\langle 2 \rangle}, \cdots, K''^{\langle \varepsilon -1 \rangle}$ across rounds is that each $i$-th round's evaluation of function $F_{\epsilon'}$ and $G_{\epsilon}$ is done modulo $p^{\varepsilon - i}$, which produces new $p^{\varepsilon - i}$-multiple overflow garbage values each time. 

$ $












Beneficially, the $\varepsilon - 1$ rounds of inverse-$p$ multiplications yields the effect of scaling down the plaintext $p^{\varepsilon-1}m_i \rightarrow m_i$ and the noise $k''p^{\varepsilon} \rightarrow k''p$, which has the desired noise scaling factor $p$ for standard BGV ciphertexts. 

$ $

\item \textbf{\textsf{\underline{SlotToCoeff}}:} This step works the same way as BFV's \textsf{SlotToCoeff} step: move $m_i + k''_ip$ stored in the input vector slots back to the polynomial coefficient positions by homomorphically multiplying with $\hathat W^*$. Upon completing this step, the ciphertext modulus is some value $q_{l'}$ smaller than $q_L$, because the homomorphic operation of step $4\sim6$ has consumed a few multiplicative levels. The resulting plaintext coefficients are $m_i + k'''_ip$, where $k''' > k''$ due to the additional noise generated by homomorphically running the \textsf{SlotToCoeff} step. The plaintext modulus (i.e., the noise scaling factor) and the noise scaling factor are $p$ at this point, the standard one for BGV ciphertexts. We let these polynomials be $M$ and $K'''$ each, and the output ciphertext is $\textsf{RLWE}_{S, \sigma}(M + K'''p) \bmod q_{l'}$.



\end{enumerate}



\subsubsection{Discussion} 

\para{The Reason for Modulus Switch from $q_l \rightarrow \hat{q}$}: BGV switches the modulus from $q_l \rightarrow \hat{q}$ to eliminate the $q_l$-multiple overflows during bootstrapping. After switching the modulus $q_l \rightarrow \hat{q}$ and then \textsf{ModRaise}, the encrypted plaintext gets the $K'\hat{q}$ overflow term, which can be reduced to $K'$ from the plaintext modulus's perspective due to the special property $\hat{q} \equiv 1 \bmod p^\varepsilon$ (where $p^\varepsilon$ is the plaintext modulus).

$ $

\para{The Choice of $\varepsilon$:} The larger $\varepsilon$ is, the greater the (base-$p$) digit-wise gap between $p^{\varepsilon-1}M$ and $K'$ becomes; thus, the less likely it is that the decryption would fail (i.e., fail to zero out $K'$). However, a larger $\varepsilon$ means the digit extraction operation would be more expensive. 

$ $


\para{Generalization to $\Delta = p^r$:} Like the case of BFV's bootstrapping (Summary~\ref*{subsubsec:bfv-bootstrapping-summary} in \autoref{subsubsec:bfv-bootstrapping-summary}), we can generalize the plaintext modulus (i.e., noise scaling factor) to $p^r$ where $p$ is a prime and $r$ can be any positive integer. 







\subsubsection{Comparing the Bootstrapping in BFV, BGV, and CKKS} 
\label{subsubsec:bootstrapping-differences}

Both BFV and BGV's bootstrapping use digit extraction, but for different purposes. In BFV, digit extraction is used to eliminate the noise in the lower-bit area. In BGV, digit extraction is used to eliminate the modulus garbage values in the lower-bit area generated by \textsf{ModRaise} from $\hat{q}\rightarrow q_L$. In addition, at each round of BGV's digit extraction, we explicitly multiply the coefficients of the ciphertext polynomials by $|p^{-1}|_{q^{\langle i \rangle}}$. In BFV, this explicit inverse-$p$ multiplication is skipped and we only conceptually re-interpret the scaling factor. 

CKKS's bootstrapping does not involve digit extraction because it has no values to eliminate in the lower-bit area. Instead, regarding the modulus garbage value \textsf{ModRaise} from $q_0 \rightarrow q_L$, this is eliminated by \textsf{EvalExp}'s homomorphic evaluation of an approximate sine function. Although CKKS's bootstrapping resets its modulus to a large value, this operation does not decrease the noise-to-message ratio, and this ratio continuously increases over homomorphic operations. 

%In the case of BFV's bootstrapping, we need homomorphic decryption (\autoref{subsubsec:bfv-bootstrapping-homomorphic-decryption}) because we need to simultaneously change the ciphertext's plaintext scaling factor from $p^{\varepsilon-1} \rightarrow \left\lfloor\dfrac{q}{p}\right\rfloor$ and the ciphertext modulus from $p^\varepsilon \rightarrow q$.For the similar reason, in the case of BGV's bootstrapping, we used digit extraction to change the noise scaling factor from  $\hat{q} \rightarrow q_L$ ((or technically, $\hat{q} \rightarrow q_{l'}$ where $\hat{q} < q_{l'} < q_L$) while keeping the noise scaling factor (i.e., the plaintext modulus) $\Delta = p^\varepsilon$. On the other hand, in the case of CKKS's bootstrapping, \textsf{ModRaise} instead of homomorphic decryption is sufficient because we only need to change the ciphertext modulus from $q_0 \rightarrow q_L$ (or technically, $q_0 \rightarrow q_{l'}$ where $q_0 < q_{l'} < q_L$) while keeping the same plaintext scaling factor $\Delta \approx \dfrac{q_l}{q_{l-1}}$.