d02-bfv.tex

The BFV scheme is designed for homomorphic addition and multiplication of integers. BFV's encoding scheme does not require such approximation issues because BFV is designed to encode only integers. Therefore, BFV guarantees exact encryption and decryption. BFV is suitable for use cases where the encrypted and decrypted values should exactly match (e.g., voting, financial computation), whereas CKKS is suitable for the use cases that tolerate tiny errors (e.g., data analytics, machine learning).  

In BFV, each plaintext is encrypted as an RLWE ciphertext. Therefore, BFV's ciphertext-to-ciphertext addition, ciphertext-to-plaintext addition, and ciphertext-to-plaintext multiplication are implemented based on GLWE's homomorphic addition and multiplication (as we learned in $\autoref{part:generic-fhe}$), with $k = 1$ to make GLWE an RLWE. 




\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}
\end{itemize}
\end{tcolorbox}

\clearpage

\subsection{Single Value Encoding}
\label{subsec:bfv-single-encoding}

BFV supports two encoding schemes: single value encoding and batch encoding. In this subsection, we will explain the single value encoding scheme. 



\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bfv-single-encoding}} BFV Encoding}}]

\textbf{\underline{Input Integer}:} Decompose the input integer $m \in \mathbb{Z}_{\geq 0}$ (i.e., 0 or any positive integer) as follows:

$m = b_{n-1}\cdot 2^{n-1} + b_{n-2}\cdot 2^{n-2} + \cdots + b_1\cdot 2^1 + b_0\cdot 2^0$  \text { } , where each $b_i \in \{0, 1\}$

$ $


\textbf{\underline{Encoded Polynomial}:} $M(X) = b_0 + b_1X + b_2X^2 + \cdots + b_{n-1}X^{n-1} \in \mathcal{R}_{\langle n, t\rangle}$

$ $

\textbf{\underline{Decoding}:} $M(X=2) = m$

\end{tcolorbox}


Let's analyze whether the encoding scheme in Summary~\ref*{subsec:bfv-single-encoding} ensures correct decoding after addition and multiplication. This is equivalent to showing that:

$\text{Decode}(\sigma(m_1) + \sigma(m_2)) = m_1 + m_2$ \textcolor{red}{$\rhd$ where $\sigma$ is the encoding function}

$\text{Decode}(\sigma(m_1) \cdot \sigma(m_2)) = m_1 \cdot m_2$

Let $\sigma(m_1) = M_1(X)$ and $\sigma(m_2) = M_2(X)$. Then, 

$\text{Decode}(\sigma(m_1) + \sigma(m_2)) = \text{Decode}(M_1(X) + M_2(X))$


$= \text{Decode}(M_{1+2}(X))$ \textcolor{red}{$\rhd$ where $M_{1+2}(X) = M_1(X) + M_2(X)$}

$= M_{1+2}(2)$ \textcolor{red}{$\rhd$ since decoding is evaluating the polynomial at $X = 2$}

$= M_{1}(2) + M_{2}(2)$ \textcolor{red}{$\rhd$ since evaluating $M_{1+2}(X)$ at $X=2$ is computationally the same as splitting $M_{1+2}(X)$ into $M_{1}(X)$ and $M_{2}(X)$, evaluating $M_1(2)$ and $M_2(2)$ and summing them}

$ $

Similarly, the decoding preserves correctness over multiplication as well:

$\text{Decode}(\sigma(m_1) \cdot \sigma(m_2)) = \text{Decode}(M_1(X) \cdot M_2(X))$

$= \text{Decode}(M_{1\cdot2}(X))$ \textcolor{red}{$\rhd$ where $M_{1\cdot2}(X) = M_1(X) \cdot M_2(X)$}

$= M_{1\cdot2}(2)$ \textcolor{red}{$\rhd$ since decoding is evaluating the polynomial at $X = 2$}

$= M_{1}(2) \cdot M_{2}(2)$ \textcolor{red}{$\rhd$ since evaluating $M_{1\cdot2}(X)$ at $X=2$ is computationally the same as splitting $M_{1\cdot2}(X)$ into $M_{1}(X)$ and $M_{2}(X)$, evaluating $M_1(2)$ and $M_2(2)$ and multiplying them}




$ $

Therefore, the single value encoding scheme preserves the correctness of decoding after addition and multiplication. 

$ $

The encoding scheme in Summary~\ref*{subsec:bfv-single-encoding} can be validly used for fully homomorphic encryption only if the multiplication of the encoded polynomials do not exceed the polynomial ring's degree $n$, because once the degree gets reduced due to an overflow, the evaluated values of polynomials lose consistency. Also, the coefficients of polynomials should not wrap modulo $t$ after additions or multiplications. 
Due to these constraints, the single value encoding is not a good choice for fully homomorphic encryption. Also, the single value encoding is computationally inefficient, because each polynomial can encode only a single value even if it holds $n$ coefficients. 


\subsection{Batch Encoding}
\label{subsec:bfv-batch-encoding}

While the single-value encoding scheme (\autoref{subsec:bfv-single-encoding}) encodes \& decodes each individual value one at a time, the batch encoding scheme does the same for a huge list of values simultaneously using a large dimensional vector. Therefore, batch encoding is more efficient than single-value encoding. Furthermore, batch-encoded values can be homomorphically added or multiplied simultaneously element-wise by vector-to-vector addition and Hadamard product. Therefore, the homomorphic operation of batch-encoded values can be processed more efficiently in a SIMD (single-instruction-multiple-data) manner than single-value encoded ones. 

BFV's encoding converts an $n$-dimensional integer input slot vector $\vec{v} = (v_0, v_1, v_2, \cdots v_{n-1})$ modulo $t$ into another $n$-dimensional vector $\vec{m} = (m_0, m_1, m_2, \cdots m_{n-1})$ modulo $t$, which are the coefficients of the encoded $(n-1)$-degree (or lesser-degree) polynomial $M(X) \in \mathbb{Z}_t[X] / (X^n + 1)$. 

$ $

\subsubsection{\textsf{Encoding\textsubscript{1}}}  
\label{subsubsec:bfv-encoding-1} 

In \autoref{subsec:poly-vector-transformation}, we learned that an $(n-1)$-degree (or lesser degree) polynomial can be isomorphically mapped to an $n$-dimensional vector based on the mapping $\sigma$ (we notate $\sigma_c$ in \autoref{subsec:poly-vector-transformation} as $\sigma$ for simplicity): 

$\sigma: M(X) \in \mathbb{Z}_t[X]/(X^n + 1) \longrightarrow  (M(\omega),M(\omega^3),M(\omega^5), \cdots, M(\omega^{2n-1})) \in \mathbb{Z}_t^n$

$ $

, which evaluates the polynomial $M(X)$ at $n$ distinct $(\mu=2n)$-th primitive roots of unity: $\omega, \omega^3, \omega^5, \cdots, \omega^{2n-1}$. Let $\vec{m}$ be a vector that contains $n$ coefficients of the polynomial $M(X)$. Then, we can express the mapping $\sigma$ as follows: 

$\vec{v} = W^T \cdot \vec{m}$

$ $

, where $W^T$ is as follows: 

$W^T = \begin{bmatrix}
1 & (\omega) & (\omega)^2 & \cdots & (\omega)^{n-1}\\
1 & (\omega^3) & (\omega^3)^2 & \cdots & (\omega^3)^{n-1}\\
1 & (\omega^5) & (\omega^5)^2 & \cdots & (\omega^5)^{n-1}\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & (\omega^{2n-1}) & (\omega^{2n-1})^2 & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix}$  \textcolor{red}{ \text{ } \# $W^T$ is a transpose of $W$ described in \autoref{subsec:poly-vector-transformation}}

$ $

Note that the dot product between each row of $W^T$ and $\vec{m}$ computes the evaluation of $M(X)$ at each $X = \{w, w^3, w^5, \cdots, w^{2n-1}\}$. In the BFV encoding scheme, the \textsf{Encoding\textsubscript{1}} process encodes an $n$-dimensional input slot vector $\vec{v}$ $\in \mathbb{Z}_t$ into a plaintext polynomial $M(X) \in \mathbb{Z}_t[X] / (X^n + 1)$, and the \textsf{Decoding\textsubscript{2}} process decodes $M(X)$ back to $\vec{v}$. Since $W^T \cdot \vec{m}$ gives us $\vec{v}$ which is a decoding of $M(X)$, we call $W^T$ a decoding matrix. Meanwhile, the goal of \textsf{Encoding\textsubscript{1}} is to encode $\vec{v}$ into $M(X)$ so that we can do homomorphic computations based on $M(X)$. Given the relation $\vec{v} = W^T \cdot \vec{m}$, the encoding formula can be derived as follows:

$(W^T)^{-1} \cdot \vec{v} = (W^T)^{-1} W^T \cdot \vec{m}$

$\vec{m} = (W^T)^{-1} \cdot \vec{v}$

$ $

Therefore, we need to find out what $(W^T)^{-1}$ is, the inverse of $W^T$ as the encoding matrix. But we already learned from Theorem~\ref*{subsec:vandermonde-euler} (in \autoref{subsec:vandermonde-euler}) that $V^{-1} = \dfrac{V^T \cdot I_n^R}{n}$, where $V = W^T$ and $V^T = W$. In other words, $(W^T)^{-1} = \dfrac{W \cdot I_n^R}{n}$. Therefore, we can express the BFV encoding formula as: 

$\vec{m} = (W^T)^{-1} \cdot \vec{v} = \dfrac{W \cdot I_n^R \cdot \vec{v}}{n}$, \text{ } where

$ $

$W =  \begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
(\omega) & (\omega^3) & (\omega^5) & \cdots & (\omega^{2n-1})\\
(\omega)^2 & (\omega^3)^2 & (\omega^5)^2 & \cdots & (\omega^{2n-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & (\omega^5)^{n-1} & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix}$

$= \begin{bmatrix}
1 & 1 & \cdots & 1 & 1 & \cdots & 1 & 1\\
(\omega) & (\omega^3) & \cdots & (\omega^{\frac{n}{2} - 1}) & (\omega^{-(\frac{n}{2} - 1)}) & \cdots & (\omega^{-3}) & (\omega^{-1})\\
(\omega)^2 & (\omega^3)^2 & \cdots & (\omega^{\frac{n}{2} - 1})^2 & (\omega^{-(\frac{n}{2} - 1)})^2 & \cdots & (\omega^{-3})^2 & (\omega^{-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & \cdots & (\omega^{\frac{n}{2} - 1})^{n-1} & (\omega^{-(\frac{n}{2} - 1)})^{n-1} & \cdots & (\omega^{-3})^{n-1} & (\omega^{-1})^{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}).

In \autoref{subsec:poly-vector-transformation}, we learned that $W$ is a valid basis of the $n$-dimensional vector space. Therefore, $\dfrac{W \cdot \vec{v}}{n} = \vec{m}$ is guaranteed to be a unique vector corresponding to each $\vec{v}$ in the $n$-dimensional vector space $\mathbb{Z}_t^{n}$ (refer to Theorem~\ref*{subsec:projection} in \autoref{subsec:projection}), and thereby the polynomial $M(X)$ comprising the $n$ elements of $\vec{m}$ as coefficients is a unique polynomial bi-jective to $\vec{v}$. 

Note that by computing $\dfrac{W \cdot I_n^R \cdot \vec{v}}{n}$
, we transform the input slot vector $\vec{v}$ into another vector $\vec{m}$ in the same vector space $\mathbb{Z}_t^{n}$, while preserving isomorphism between these two vectors (i.e., bi-jective one-to-one mappings and homomorphism on the $(+, \cdot)$ operations). 

\subsubsection{\textsf{Encoding\textsubscript{2}}}  

Once we have the $n$-dimensional vector $\vec{m}$, we scale (i.e., multiply) it by some scaling factor $\Delta = \left\lfloor \dfrac{q}{t} \right\rfloor$, where $q$ is the ciphertext modulus. We scale $\vec{m}$ by $\Delta$ and make it $\Delta \vec{m}$. 
The $n$ integers in $\Delta\vec{m}$ will be used as $n$ coefficients of the plaintext polynomial for RLWE encryption. The finally encoded plaintext polynomial $\Delta M = \sum\limits_{i=0}^{n-1}\Delta m_iX^i$. 


\subsubsection{\textsf{Decoding\textsubscript{1}}}  
\label{subsubsec:bfv-enc-dec-decoding1} 

Once an RLWE ciphertext is (first-half) decrypted to $\Delta M = \sum\limits_{i=0}^{n-1}\Delta m_iX^i$, we compute $\dfrac{\Delta\vec{m}}{\Delta} = \vec{m}$.




\subsubsection{\textsf{Decoding\textsubscript{2}}}  


In \autoref{subsubsec:bfv-encoding-1}, we already derived the decoding formula that transforms an $(n-1)$-degree polynomial having integer modulo $t$ coefficients into an $n$-dimensional input slot vector as follows: 

$\vec{v} = W^T \cdot \vec{m}$


\subsubsection{Summary}
\label{subsubsec:bfv-encoding-summary}

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsubsec:bfv-encoding-summary}} BFV's Encoding and Decoding}}]



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

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

\textbf{\underline{Encoding}} 
\begin{enumerate}

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

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

$W =  \begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
(\omega) & (\omega^3) & (\omega^5) & \cdots & (\omega^{2n-1})\\
(\omega)^2 & (\omega^3)^2 & (\omega^5)^2 & \cdots & (\omega^{2n-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & (\omega^5)^{n-1} & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix}$

$= \begin{bmatrix}
1 & 1 & \cdots & 1 & 1 & \cdots & 1 & 1\\
(\omega) & (\omega^3) & \cdots & (\omega^{\frac{n}{2} - 1}) & (\omega^{-(\frac{n}{2} - 1)}) & \cdots & (\omega^{-3}) & (\omega^{-1})\\
(\omega)^2 & (\omega^3)^2 & \cdots & (\omega^{\frac{n}{2} - 1})^2 & (\omega^{-(\frac{n}{2} - 1)})^2 & \cdots & (\omega^{-3})^2 & (\omega^{-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & \cdots & (\omega^{\frac{n}{2} - 1})^{n-1} & (\omega^{-(\frac{n}{2} - 1)})^{n-1} & \cdots & (\omega^{-3})^{n-1} & (\omega^{-1})^{n-1}\\
\end{bmatrix}$

$ $

, where $\omega$ is a primitive $2n$-th root of unity modulo $t$. 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}).

$ $

\item Convert $\vec{m}$ into a scaled integer vector $\Delta\vec{m}$, where $1 \leq \Delta \leq \lfloor \dfrac{q}{t}\rfloor$ is a scaling factor. If $\Delta$ is too close to 1 (i.e., $t$ is too big), the \textbf{noise budget} will become too small (making decryption fail easily). If $\Delta$ is too close to $q$ (i.e., $t$ is too small), the \textbf{message capacity} will become too small (i.e., the plaintext modulus $t$ limits the range of values that can be encoded). The finally encoded plaintext polynomial $\Delta M = \sum\limits_{i=0}^{n-1} \Delta m_i X^i \text{ } \in \mathbb{Z}_q[X] / (X^n + 1)$. %The rounding of $\lceil \Delta \vec{m} \rfloor$ during the encoding process makes CKKS an approximate FHE scheme. 

\end{enumerate}

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

\textbf{\underline{Decoding}:} From the plaintext polynomial $\Delta M = \sum\limits_{i=0}^{n-1}\Delta m_iX^i$, recover $\vec{m} = \dfrac{\Delta \vec{m}}{\Delta}$. Then,
compute $\vec{v} = W^T \cdot \vec{m}$.

\end{tcolorbox}


%\para{BFV's Encoding Range:} \autoref{tab:polynomial-encoding-capacity-integer} depicts the range of input values that can be encoded by the polynomials $M(X) \in \mathcal{R}_{\langle n, t \rangle}$ over $X \in \mathbb{Z}_t$. As illustrated in \autoref{tab:polynomial-encoding-capacity-integer}, the encoding range of integer inputs is determined by the size of the $n$ and $t$ parameters. Therefore, these two parameters should be chosen sufficiently large enough to encode all values that can be used by an application. 

However, Summary~\ref*{subsubsec:bfv-encoding-summary} is not the final version of BFV's batch encoding. In \autoref{subsec:bfv-rotation}, we will explain how to homomorphically rotate the input vector slots without decrypting the ciphertext that encapsulates it. To support such homomorphic rotation, we will need to slightly update the encoding scheme explained in Summary~\ref*{subsubsec:bfv-encoding-summary}. We will explain how to do this in \autoref{subsec:bfv-rotation}, and BFV's final encoding scheme is summarized in Summary~\ref*{subsubsec:bfv-rotation-summary} in \autoref{subsubsec:bfv-rotation-summary}.


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

BFV encrypts and decrypts ciphertexts based on the RLWE cryptosystem (\autoref{sec:rlwe}) with the sign of each $A\cdot S$ term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative version of the GLWE cryptosystem (\autoref{subsec:glwe-alternative}) with $k = 1$. Thus, BFV's encryption and decryption formulas are as follows: 



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

\textbf{\underline{Initial Setup}:} $\Delta=\left\lfloor\dfrac{q}{t}\right\rfloor \text{ is a plaintext scaling factor for polynomial encoding}, \text{ } S \xleftarrow{\$} \mathcal{R}_{\langle n, \textit{tern} \rangle}$

, where plaintext modulus $t$ is either a prime ($p$) or a power of prime ($p^r$), and ciphertext modulus $q \gg t$. As for the coefficients of polynomial $S$, they are ternary (i.e., $\{-1, 0, 1\}$).

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

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


$ $

\begin{enumerate}


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

\item $\textsf{RLWE}_{S,\sigma}(\Delta M + 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$ 

$\textsf{RLWE}^{-1}_{S,\sigma}(\textsf{ct}) = \left\lceil\dfrac{B + A \cdot S \bmod q}{\Delta}\right\rfloor \bmod t = \left\lceil\dfrac{\Delta M + E}{\Delta}\right\rfloor \bmod t = M \bmod t$

(The noise $E = \sum\limits_{i=0}^{n-1}e_iX^i$ gets eliminated by the rounding process) 



$ $

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

As explained in Summary~\ref*{subsubsec:lwe-noise-bound} (in \autoref{subsubsec:lwe-noise-bound}), the noise bound is $|-\epsilon k_i t + e_i| < \dfrac{\Delta}{2}$, where $k_i$ is each coefficient of the polynomial $K$ that accounts for the $t$-multiple overflows of the coefficients of the plaintext polynomial updated across homomorphic operations. 

\end{tcolorbox}


In this section, we will often write $\textsf{RLWE}_{S,\sigma}(\Delta  M + E)$ as $\textsf{RLWE}_{S,\sigma}(\Delta  M)$ for simplicity, because $\textsf{RLWE}_{S,\sigma}(\Delta M + E) \approx \textsf{RLWE}_{S,\sigma}(\Delta M)$ (i.e., they decrypt to the same message). Even in the case that we write $\textsf{RLWE}_{S,\sigma}(\Delta  M)$ instead of $\textsf{RLWE}_{S,\sigma}(\Delta  M + E)$, you should assume this as an encryption of $\Delta  M + E$ (i.e., the noise is included inside the scaled message). 


We will explain the conditions for BFV's correct decryption in more detail in \autoref{subsubsec:bfv-noise-analysis}.



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

BFV's ciphertext-to-ciphertext addition uses RLWE's ciphertext-to-ciphertext addition scheme with the sign of the $A\cdot S$ term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative GLWE version's (\autoref{subsec:glwe-alternative}) ciphertext-to-ciphertext addition scheme with $k = 1$. 


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bfv-add-cipher}} BFV Ciphertext-to-Ciphertext Addition}}]
$\textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} ) + \textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 2 \rangle} + 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}(\Delta(M^{\langle 1 \rangle} + M^{\langle 2 \rangle}) + E^{\langle 1 \rangle} + E^{\langle 2 \rangle})$
\end{tcolorbox}


\subsubsection{Noise Bound Analysis}
\label{subsubsec:bfv-noise-analysis}

In the last part of Summary~\ref*{subsec:bfv-enc-dec} (in \autoref{subsec:bfv-enc-dec}), we learned the noise bound conditions for BFV's correct decryption. In this subsection, we will explain how this condition holds in more detail by walking through BFV's ciphertext-to-ciphertext addition. 

Let's denote the homomorphically added ciphertext as follows: 

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

$ $

Applying the first step of decryption to it yields the following intermediate result:

$B^{\langle 3 \rangle} + A^{\langle 3 \rangle}\cdot S \bmod q$

$B^{\langle 1 \rangle} + B^{\langle 2 \rangle} + A^{\langle 1 \rangle}\cdot S + A^{\langle 2 \rangle}\cdot S \bmod q$

$= (-A^{\langle 1 \rangle}\cdot S + \Delta M^{\langle 1\rangle} + E^{\langle 1 \rangle}) + (- A^{\langle 2 \rangle}\cdot S  + \Delta M^{\langle 2\rangle}  + E^{\langle 2 \rangle}) + A^{\langle 1 \rangle}\cdot S + A^{\langle 2 \rangle}\cdot S \bmod q$

$= \Delta M^{\langle 1\rangle} + E^{\langle 1 \rangle} + \Delta M^{\langle 2\rangle} + E^{\langle 2 \rangle} \bmod q $

$ $

The second step of decryption is to divide each coefficient of the above intermediate polynomial by $\Delta$, round it, and reduce it modulo $t$ as follows:

$ $

$\left\lceil\dfrac{\Delta (M^{\langle 1\rangle} + M^{\langle 2\rangle}) + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$

$ $

Correct decryption requires the above result to match the value $M^{\langle 1 + 2 \rangle} = M^{\langle 1 \rangle} + M^{\langle 2 \rangle} \bmod t$, where $M^{\langle 1 + 2 \rangle}$ is the modulo $t$-reduced final polynomial. Let's define $\epsilon = \dfrac{q}{t} - \left\lfloor\dfrac{q}{t}\right\rfloor = \dfrac{q}{t} - \Delta$. Given $q \gg t$, $\epsilon$ is a fractional value between $[0, 1)$. Now, we can re-write the above decryption term as follows:

$ $

$\left\lceil\dfrac{\Delta (M^{\langle 1\rangle} + M^{\langle 2\rangle}) + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$ 

$ $

$\left\lceil\dfrac{(\frac{q}{t} - \epsilon)\cdot (M^{\langle 1\rangle} + M^{\langle 2\rangle}) + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$ \textcolor{red}{ $\rhd$ applying $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor = \dfrac{q}{t} - \epsilon$}

$ $

$ = \left\lceil\dfrac{(\frac{q}{t} - \epsilon)\cdot (M^{\langle 1 + 2\rangle} + t\cdot K) + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$ 

\textcolor{red}{ $\rhd$ where $t \cdot K$ represents the $t$-multiple overflows generated by the modulo addition of $M^{\langle 1\rangle} + M^{\langle 2\rangle}$ }

$ $

$ $

$ = \left\lceil\dfrac{\frac{q}{t} \cdot M^{\langle 1 + 2\rangle}  - \epsilon \cdot M^{\langle 1 + 2\rangle}  + \frac{q}{t} \cdot t\cdot K  - \epsilon \cdot t\cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$ 

$ $

$ = \left\lceil\dfrac{\frac{q}{t} \cdot M^{\langle 1 + 2\rangle}  - \epsilon \cdot M^{\langle 1 + 2\rangle}  - \epsilon \cdot t\cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$ 

\textcolor{red}{ $\rhd$ since $\frac{q}{t}\cdot t = q$, and $q\cdot K \bmod q = 0$}

$ $

$ $


$ = \left\lceil\dfrac{\left\lfloor\frac{q}{t}\right\rfloor \cdot M^{\langle 1 + 2\rangle} + \epsilon \cdot M^{\langle 1 + 2\rangle} - \epsilon \cdot M^{\langle 1 + 2\rangle}  - \epsilon \cdot t\cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$  

\textcolor{red}{ $\rhd$ applying  $\dfrac{q}{t} = \left\lfloor\dfrac{q}{t}\right\rfloor + \epsilon$}

$ $

$ $


$ = \left\lceil\dfrac{\left\lfloor\frac{q}{t}\right\rfloor \cdot M^{\langle 1 + 2\rangle} - \epsilon \cdot t\cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} \bmod q}{\Delta}\right\rfloor \bmod t$  

$ $

$ $

$ = \left\lceil\dfrac{\left\lfloor\frac{q}{t}\right\rfloor \cdot M^{\langle 1 + 2\rangle} - \epsilon \cdot t\cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle}}{\Delta}\right\rfloor \bmod t$  

\textcolor{red}{ $\rhd$ applying the special assumption $|\epsilon \cdot t \cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle}| < \dfrac{\Delta}{2}$ to all $n$ coefficients (see \autoref{subsubsec:lwe-noise-bound})}

$ $

$ $


$ = M^{\langle 1 + 2\rangle} + \left\lceil\dfrac{E^{\langle 1 \rangle} + E^{\langle 2 \rangle} - \epsilon \cdot t\cdot K}{\Delta}\right\rfloor \bmod t$  \textcolor{red}{ $\rhd$ since  $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$, and $\lceil M^{\langle 1 + 2\rangle} \rfloor = M^{\langle 1 + 2\rangle}$}

$ $

$ $

$ = M^{\langle 1 + 2\rangle} \bmod t$
\textcolor{red}{ $\rhd$ applying the special assumption $\epsilon \cdot t \cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} < \dfrac{\Delta}{2}$ to all $n$ coefficients}


$ $

The above final expression implies that correct decryption (i.e., $M^{\langle 1 + 2\rangle}$) is preserved if 
the special assumption $\epsilon \cdot t \cdot K + E^{\langle 1 \rangle} + E^{\langle 2 \rangle} < \dfrac{\Delta}{2}$ holds (for all $n$ coefficients of the polynomial). At a high level, the greater the ciphertext modulus $q$ becomes compared to the plaintext modulus $t$, the greater the scaling factor $\Delta$ becomes, which can sustain a greater noise budget ($E^{\langle 1 \rangle} + E^{\langle 2 \rangle}$) and greater wrapping around $t$-multiple overflows of the plaintext ($\epsilon \cdot t\cdot K$). 

This noise bound principle not only applies to homomorphic addition but also to homomorphic multiplication and rotation, which will be explained in later subsections. The term $E^{\langle 1 \rangle} + E^{\langle 2 \rangle}$ can be generalized as the cumulative noise across all homomorphic operations (e.g., additions, multiplications, rotations), and the term $\epsilon \cdot t\cdot K$ can be generalized as the amount of $t$-multiple overflows of each coefficient of the plaintext polynomial computed across homomorphic operations.



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

BFV's ciphertext-to-plaintext addition uses RLWE's ciphertext-to-plaintext addition scheme with the sign of the $A\cdot S$ term flipped in the encryption and decryption formulas. Specifically, this is equivalent to the alternative GLWE version's (\autoref{subsec:glwe-alternative}) ciphertext-to-plaintext addition scheme (\autoref{sec:glwe-add-plain}) with $k = 1$.  


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

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

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

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



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


BFV's ciphertext-to-plaintext multiplication uses RLWE's ciphertext-to-plaintext multiplication scheme with the sign of the $A\cdot S$ term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative GLWE version's (\autoref{subsec:glwe-alternative}) ciphertext-to-plaintext multiplication scheme (\autoref{sec:glwe-mult-plain}) with $k = 1$.   


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

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

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

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




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

\noindent \textbf{- Reference 1:} 
\href{https://www.inferati.com/blog/fhe-schemes-bfv}{Introduction to the BFV encryption scheme}~\cite{inferati-bfv}

\noindent \textbf{- Reference 2:} 
\href{https://eprint.iacr.org/2012/144.pdf}{Somewhat Partially Fully Homomorphic Encryption}~\cite{cryptoeprint:2012/144}

%\noindent \textbf{- Reference 3:} 
%\href{https://eprint.iacr.org/2016/510.pdf}{A Full RNS Variant $of FV like Somewhat Homomorphic Encryption Schemes}~\cite{cryptoeprint:2016/510}


Given two ciphertexts $\textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 1\rangle })$ and $\textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 2\rangle})$, the goal of ciphertext-to-ciphertext multiplication is to derive a new ciphertext whose decryption is $\Delta M^{\langle 1 \rangle} M^{\langle 2 \rangle}$. Ciphertext-to-ciphertext multiplication is more complex than ciphertext-to-plaintext multiplication. It comprises four steps: (1) \textsf{ModRaise}; (2) polynomial multiplication; (3) relinearization; and (4) rescaling. 

For better understanding, we will explain BFV's ciphertext-to-ciphertext multiplication based on the alternate version of RLWE (Theorem~\ref*{subsec:glwe-alternative} in \autoref{subsec:glwe-alternative}), where the sign of the $AS$ term is flipped in the encryption and decryption formulas.

\subsubsection{\textsf{ModRaise}}
\label{subsubsec:bfv-mult-cipher-modraise}

We learned from Summary~\ref*{subsec:bfv-enc-dec} (in \autoref{subsec:bfv-enc-dec}) that a BFV ciphertext whose ciphertext modulus is $q$ has the (decryption) relation: $\Delta M + E = A\cdot S + B - K \cdot q$, where $K \cdot q$ stands for modulo reduction by $q$. \textsf{ModRaise} is a process of forcibly raising the modulus of a ciphertext from $q \rightarrow Q$, where $q \ll Q$. Suppose we modify the modulus of ciphertext $(A, B)$ from $q$ to $Q$, where $Q = q \cdot \Delta$ (remember $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$). Then, the decryption of the \textit{mod-raised} ciphertext will output $A\cdot S + B \bmod Q$. However, since each polynomial coefficient of $A$ and $B$ is less than $q$ and each polynomial coefficient of $S$ is either $\{-1, 0, 1\}$, the resulting polynomial of $A\cdot S + B$ is guaranteed to have each coefficient strictly less than $Q$ even without modulo reduction by $Q$-- this is because $(q-1)\cdot n + (q-1) < Q$, where $(q-1)\cdot n$ is the maximum possible coefficient of $A \cdot S$ and $(q-1)$ is the maximum possible coefficient of $B$. And as mentioned before, we know the relation: $A\cdot S + B = \Delta M + E + Kq$. Therefore, the decryption of the \textit{mod-raised} ciphertext $(A, B) \bmod Q$ is as follows:

$\Delta M + E + Kq \bmod Q = \Delta M + E + Kq$ \textcolor{red}{ $\rhd$  since $\Delta M + E + Kq < Q$} 

$ $

The first step of BFV's ciphertext-to-ciphertext multiplication is to \textit{mod-raise} the two input ciphertexts $(A^{\langle 1 \rangle}, B^{\langle 1 \rangle}) \bmod q$ and $(A^{\langle 2 \rangle}, B^{\langle 2 \rangle}) \bmod q$  
from $q \rightarrow Q$ (where $Q = q\cdot \Delta$) as follows: 

$(A^{\langle 1 \rangle}, B^{\langle 1 \rangle}) \bmod Q$

$(A^{\langle 2 \rangle}, B^{\langle 2 \rangle}) \bmod Q$

$ $

After \textsf{ModRaise}, the decryption of these two ciphertexts would be the following: 

$A^{\langle 1 \rangle} \cdot S + B^{\langle 1 \rangle} = \Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q < Q$

$A^{\langle 2 \rangle} \cdot S + B^{\langle 2 \rangle} = \Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q < Q$


$ $

Therefore, the \textit{mod-raised} ciphertexts have the following form: 

$\textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 1 \rangle} + K_1q) = (A^{\langle 1 \rangle}, B^{\langle 1 \rangle}) \bmod Q$

$\textsf{RLWE}_{S, \sigma}(\Delta M^{\langle 2 \rangle} + K_2q) = (A^{\langle 2 \rangle}, B^{\langle 2 \rangle}) \bmod Q$


\subsubsection{Polynomial Multiplication}
\label{subsubsec:bfv-mult-cipher-multiplication}

Our next goal is to derive a new ciphertext which encrypts 
$(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q)$. 

First, we can derive the following relation: 

$(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q)$

$ = (A^{\langle 1 \rangle} \cdot S + B^{\langle 1 \rangle}) \cdot (A^{\langle 2 \rangle} \cdot S + B^{\langle 2 \rangle})$

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



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



$ $

Meanwhile, we also have the following relations:

$\textsf{RLWE}_{S, \sigma}^{-1}(\Delta M^{\langle 1 \rangle} + K_1q) = \Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q$

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

$ $

Combining all these, we reach the following relation: 

$\textsf{RLWE}_{S, \sigma}^{-1}(\Delta M^{\langle 1 \rangle} + K_1q) \cdot \textsf{RLWE}_{S, \sigma}^{-1}(\Delta M^{\langle 2 \rangle} + K_2q) = D_0 + D_1\cdot S + D_2\cdot S^2$

$ $

Notice that $D_0, D_1,$ and $D_2$ are known values as ciphertext components, whereas $S$ is only known to the private key owner. Therefore, we can view $D_0 + D_1\cdot S + D_2\cdot S^2$ as a decryption formula such that given the ciphertext components $D_0, D_1, D_2$ and the private key $S$, one can derive $(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q)$. In other words, we can let $(D_0, D_1, D_2)$ be a new form of ciphertext which can be decrypted by $S$ into $(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q)$. 

However, $(D_0, D_1, D_2)$ is not in the RLWE ciphertext format, because it has 3 components instead of 2. Having 3 ciphertext components is computationally inefficient, as its decryption involves a square root of $S$ (i.e., $ S^2$). Over consequent ciphertext-to-ciphertext multiplications, this $S$ term will double its exponents as $S^4, S^8, \cdots$ as well as the number of ciphertext components, which would exponentially increase the computational overhead of decryption. Therefore, we want to convert the intermediate ciphertext format $(D_0, D_1, D_2)$ into a regular BFV ciphertext format that has two polynomials as ciphertext components. This conversion process is called a relinearization process (which will be explained in the next subsection). 



\subsubsection{Relinearization}
\label{subsubsec:bfv-mult-cipher-relinearization}

Relinearization is a process of converting the polynomial triplet $(D_0, D_1, D_2) \in \mathcal{R}_{\langle n, Q \rangle}^{3}$ into two RLWE ciphertexts $\textsf{ct}_\alpha$ and $\textsf{ct}_\beta$ which hold the relation: $D_0 + D_1 S + D_2 S^2 = \textsf{RLWE}^{-1}_{S, \sigma}(\textsf{ct}_\alpha + \textsf{ct}_\beta)$. 

In the formula $D_0 + D_1 S + D_2 S^2$, we can re-write $D_0 + D_1 S$ as a \textit{synthetic} RLWE ciphertext $\textsf{ct}_\alpha = (D_1, D_0)$, which can be decrypted by $S$ into $D_1 S + D_0$. Similarly, our next task is to derive a synthetic RLWE ciphertext $\textsf{ct}_\beta$ whose decryption is $D_2 \cdot S^2$ (i.e., $\textsf{RLWE}_{S, \sigma}^{-1}(\textsf{ct}_\beta) = D_2\cdot S^2$). 

A naive way of creating a ciphertext that encrypts $D_2 \cdot S^2$ is as follows: we encrypt $S^2$ into an RLWE ciphertext as $\textsf{RLWE}_{S, \sigma}(S^2) = (A^{\langle s \rangle}, B^{\langle s \rangle})$ such that $A^{\langle s \rangle}\cdot S + B^{\langle s \rangle} = S^2 + E^{\langle s \rangle} \bmod Q$ (where the ciphertext modulus is $Q$ and the plaintext scaling factor $\Delta = 1$). Then, we perform a ciphertext-to-plaintext multiplication (\autoref{sec:glwe-mult-plain}) with $D_2$, treating $D_2$ as a plaintext polynomial in modulo $Q$. However, this approach does not work in practice, because computing $D_2 \cdot \textsf{RLWE}_{S, \sigma}(S^2)$ generates a huge noise as follows:

$D_2 \cdot (A^{\langle s \rangle}, B^{\langle s \rangle}) = (D_2\cdot A^{\langle s \rangle}, D_2 \cdot B^{\langle s \rangle})$

$ $

, whose decryption is:

$D_2\cdot A^{\langle s \rangle} \cdot S + D_2\cdot B^{\langle s \rangle} = D_2 \cdot S^2 + D_2\cdot E^{\langle s \rangle} \pmod Q$ 

$ $

. In the above decrypted expression $D_2S^2 + D_2E^{\langle s \rangle} \bmod Q$, the term $D_2S^2$ is okay to be reduced modulo $Q$, because this term is originally allowed to be reduced modulo $Q$ in the final decryption formula $D_0 + D_1S + D_2S^2 \bmod Q$ as well. However, the problematic term is the noise $D_2\cdot E^{\langle s \rangle}$, because its coefficients can be any value in $[0, Q - 1]$ (since each coefficient of polynomial $D_2 = A^{\langle 1 \rangle} A^{\langle 2 \rangle}$ can be any value in $[0, Q - 1]$). Such a huge noise is not allowed for correct final decryption. 

To avoid this noise issue, an improved solution is to express the RLWE ciphertext that encrypts $D_2 S^2$ as additions of multiple RLWE ciphertexts with small noises by using the gadget decomposition technique (\autoref{subsec:gadget-decomposition}). For this, we use an RLev ciphertext (\autoref{sec:glev}) that encrypts $S^2$. Suppose our gadget vector is $\vec{g} = \Bigg(\dfrac{Q}{\beta}, \dfrac{Q}{\beta^2}, \dfrac{Q}{\beta^3}, \cdots, \dfrac{Q}{\beta^l}\Bigg)$. Remember that our goal is to find $\textsf{ct}_\beta = \textsf{RLWE}_{S, \sigma}( S^2 \cdot D_2)$ given known $D_2$, unknown $S$, and known $\textsf{RLev}_{S, \sigma}^{\beta, l}(S^2) = \left\{\textsf{RLWE}_{S, \sigma}\left(\dfrac{Q}{\beta^i}\cdot S\right)\right\}_{i=1}^{l}$. Then, we can derive $\textsf{ct}_\beta$ as follows:

$\textsf{ct}_\beta = \textsf{RLWE}_{S, \sigma}(S^2 \cdot D_2)$

$= \textsf{RLWE}_{S, \sigma}\left( S^2 \cdot \left(D_{2,1}\dfrac{Q}{\beta} + D_{2,2}\dfrac{Q}{\beta^2} + \cdots D_{2,l}\dfrac{Q}{\beta^l}\right)\right)$ \textcolor{red}{  $\rhd$ by decomposing $D_2$}

$= \textsf{RLWE}_{S, \sigma}\left( S^2 \cdot D_{2,1} \cdot \dfrac{Q}{\beta}\right) + \textsf{RLWE}_{S, \sigma}\left( S^2 \cdot D_{2,2} \cdot \dfrac{Q}{\beta^2}\right) + \cdots + \textsf{RLWE}_{S, \sigma}\left( S^2 \cdot D_{2,l} \cdot \dfrac{Q}{\beta^l}\right)$ 

$= D_{2,1}\cdot\textsf{RLWE}_{S, \sigma}\left( S^2 \cdot \dfrac{Q}{\beta}\right) + D_{2,2}\cdot\textsf{RLWE}_{S, \sigma}\left( S^2 \cdot \dfrac{Q}{\beta^2}\right) + \cdots + D_{2,l}\cdot\textsf{RLWE}_{S, \sigma}\left( S^2 \cdot \dfrac{Q}{\beta^l}\right)$ 
\textcolor{red}{ $\rhd$ where each \textsf{RLWE} ciphertext is an encryption of $S^2\dfrac{Q}{\beta}, S^2\dfrac{Q}{\beta^2}, \cdots, S^2\dfrac{Q}{\beta^l}$ as plaintext with the plaintext scaling factor $\Delta = 1$}

$ $

$= \bm{\langle} \textsf{Decomp}^{\beta, l}(D_2), \text{ } \textsf{RLev}_{S, \sigma}^{\beta, l}( S^2) \bm{\rangle}$ \textcolor{red}{  $\rhd$ inner product of \textsf{Decomp} and \textsf{RLev} treating them as vectors}

$ $

If we decrypt the above, we get the following:

$\textsf{RLWE}_{S, \sigma}^{-1}(\textsf{ct}_\beta = \bm{\langle} \textsf{Decomp}^{\beta, l}(D_2), \text{ } \textsf{RLev}_{S, \sigma}^{\beta, l}( S^2) \bm{\rangle} \bm{)}$ \textcolor{red}{ $\rhd$ the scaling factors of $\textsf{RLev}_{S, \sigma}^{\beta, l}( S^2)$ are all 1}

$= D_{2,1}\cdot\left(E_1' +  S^2\dfrac{Q}{\beta}\right) + D_{2,2}\cdot\left(E_2' +  S^2\dfrac{Q}{\beta^2}\right) + \cdots + D_{2,l}\cdot\left(E_l' +  S^2\dfrac{Q}{\beta^l}\right)$ \textcolor{red}{ \text{ } \# where each $E_i'$ is a noise embedded in $\textsf{RLWE}_{S, \sigma}\left(S^2\cdot\dfrac{Q}{\beta^i}\right)$}

$ $

$= \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) +  S^2\cdot\left(D_{2,1}\dfrac{Q}{\beta} + D_{2,2}\dfrac{Q}{\beta^2} + \cdots + D_{2, l}\dfrac{Q}{\beta^l}\right)$

$= \sum\limits_{i=1}^{l} \epsilon_{i} + D_2\cdot S^2$ \textcolor{red}{ \text{ } \# where each $\epsilon_i = E_i'\cdot D_{2,i}$}

$\approx D_2\cdot S^2$ \textcolor{red}{ \text{ } \# $\sum\limits_{i=1}^{l} \epsilon_{i} \ll D_2\cdot E''$, where $E''$ is the noise that could've been embedded in $\textsf{RLWE}_{S, \sigma}\bm(S^2\bm)$}

$ $

Therefore, we get the following comprehensive relation:


$\textsf{RLWE}_{S, \sigma}^{-1}(\Delta M^{\langle 1 \rangle} + K_1q) \cdot \textsf{RLWE}_{S, \sigma}^{-1}(\Delta M^{\langle 2 \rangle} + K_2q) \bmod Q$

$= (\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q) \bmod Q$

$ = (A^{\langle 1 \rangle} \cdot S + B^{\langle 1 \rangle}) \cdot (A^{\langle 2 \rangle} \cdot S + B^{\langle 2 \rangle})  \bmod Q$

$ = D_0 + D_1\cdot S + D_2\cdot S^2  \bmod Q$ \textcolor{red}{ $\rhd$ $D_0 = B^{\langle 1 \rangle} B^{\langle 2 \rangle}$, \text{ } $D_1 = A^{\langle 1 \rangle} B^{\langle 2 \rangle} + A^{\langle 2 \rangle} B^{\langle 1 \rangle}$, \text{ } $D_2 = A^{\langle 1 \rangle} A^{\langle 2 \rangle}$}

$ = \textsf{RLWE}_{S, \sigma}^{-1}(\textsf{ct}_\alpha) + \textsf{RLWE}_{S, \sigma}^{-1}(\textsf{ct}_\beta) - \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})  \bmod Q$ 

\textcolor{red}{ $\rhd$ $\textsf{ct}_\alpha = (D_1, D_0) = (A_\alpha, B_\beta)$, \text{ } $\textsf{ct}_\beta = \langle \textsf{Decomp}^{\beta, l}(D_2), \textsf{RLev}_{S, \sigma}^{\beta, l}(S^2) \rangle = (A_\beta, B_\beta)$}

$ $

$ = \textsf{RLWE}_{S, \sigma}^{-1}(\textsf{ct}_\alpha + \textsf{ct}_\beta) - \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})  \bmod Q$

$ = \textsf{RLWE}_{S, \sigma}^{-1}\bm((A_{\alpha+\beta}, B_{\alpha+\beta})\bm) - \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) \bmod Q$  \textcolor{red}{ $\rhd$ $A_{\alpha+\beta} = A_{\alpha} + A_\beta$, \text{ } $B_{\alpha + \beta} = B_\alpha + B_\beta$}


$ $

From the above, we extract the following relation: 

$(\Delta M^{\langle 1 \rangle} + E^{\langle 1 \rangle} + K_1q) \cdot (\Delta M^{\langle 2 \rangle} + E^{\langle 2 \rangle} + K_2q) \bmod Q$

$=  \Delta^2M^{\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}) + q\cdot(\Delta M^{\langle 1 \rangle}K_2 + \Delta M^{\langle 2 \rangle}K_1 + E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + K_1 K_2 q^2 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} \bmod Q$

$= \textsf{RLWE}_{S, \sigma}^{-1}\bm((A_{\alpha+\beta}, B_{\alpha+\beta})\bm) - \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) \bmod Q$  

$ $

We can re-write the above relation as follows:


$\textsf{RLWE}_{S, \sigma}^{-1}\bm((A_{\alpha+\beta}, B_{\alpha+\beta})\bm) = A_{\alpha+\beta}\cdot S + B_{\alpha+\beta} \bmod Q$

$ = \Delta^2M^{\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}) + q\cdot(\Delta M^{\langle 1 \rangle}K_2 + \Delta M^{\langle 2 \rangle}K_1 + E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + K_1 K_2 q^2 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) \bmod Q$ 

$ $

To verbally interpret the above relation, decrypting the synthetically generated ciphertext $(A_{\alpha+\beta}, B_{\alpha+\beta})$ and applying a reduction modulo $Q$ to it gives us $\Delta^2 M^{\langle 1 \rangle}M^{\langle 2 \rangle}$ with a lot of noise terms. Meanwhile, as explained in the beginning of this subsection, our goal is to derive a ciphertext whose decryption is $\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle}$, also ensuring that the decrypted ciphertext's noise is small enough to be fully eliminated by scaling down the plaintext by $\Delta$ at the end. This goal is accomplished by the final rescaling step to be explained in the next subsection. 


\subsubsection{Rescaling}
\label{subsubsec:bfv-mult-cipher-rescaling}

The rescaling step is equivalent to converting the ciphertext $(A_{\alpha+\beta}, B_{\alpha+\beta}) \bmod Q$ into $\left(\left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor, \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor\right) \bmod q$, where $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor \approx \dfrac{q}{t}$. The decryption of this rescaled ciphertext (and finally scaling down by $\Delta$) is $\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle}$. This is demonstrated below: 

$ $

$ \left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor \cdot S + \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor \bmod q$ \textcolor{red}{ $\rhd$ decryption of ciphertext $\left(\left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor, \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor\right) \bmod q$}

$ $

$ = \left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor \cdot S + \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor + K_3q$ \textcolor{red}{ $\rhd$ where $K_3q$ stands for modulo reduction by $q$}

$ $

$ = \left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor \cdot S + \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor + \dfrac{K_3Q}{\Delta}$ \textcolor{red}{ $\rhd$ since $Q = \Delta \cdot q$}


$ $

$ = \left\lceil\dfrac{1}{\Delta}\cdot (A_{\alpha+\beta}\cdot S + B_{\alpha+\beta} + K_3Q)\right\rfloor + E_r$ \textcolor{red}{ $\rhd$ $E_r$ is a rounding error}

$ $

$ = \left\lceil\dfrac{1}{\Delta}\cdot (A_{\alpha+\beta}\cdot S + B_{\alpha+\beta} \bmod Q)\right\rfloor + E_r$ 

$ $

$ = \Bigg\lceil\dfrac{1}{\Delta}\cdot ( \Delta^2M^{\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}) + $

\text{ } \text{ } $ q\cdot(\Delta M^{\langle 1 \rangle}K_2 + \Delta M^{\langle 2 \rangle}K_1 + E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + K_1 K_2 q^2 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) \bmod Q
)\Bigg\rfloor + E_r$

\textcolor{red}{ $\rhd$ as we derived at the end of \autoref{subsubsec:bfv-mult-cipher-relinearization}}

$ $

$ = \Bigg\lceil\dfrac{1}{\Delta}\cdot ( \Delta^2M^{\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}) + $

\text{ } \text{ } $ q\cdot(\Delta M^{\langle 1 \rangle}K_2 + \Delta M^{\langle 2 \rangle}K_1 + E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + K_1 K_2 q^2 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) + K_4Q
)\Bigg\rfloor + E_r$

\textcolor{red}{ $\rhd$ where $K_4Q$ stands for modulo reduction by $Q$}


$ $

$ $



$ = \Bigg\lceil\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + q\cdot (M^{\langle 1 \rangle}K_2 +  M^{\langle 2 \rangle}K_1) $

\text{ } \text{ } $+ \dfrac{1}{\Delta}\cdot q\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + \dfrac{1}{\Delta}\cdot (K_1K_2q^2 
 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})) + K_5q\Bigg\rfloor $ 

\text{ } \text{ }  \textcolor{red}{ $\rhd$ where $K_5q = K_4q + M^{\langle 1 \rangle}q K_2 + M^{\langle 2 \rangle} K_1q$}




$ $

$ $

$ = \Bigg\lceil\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + q\cdot (M^{\langle 1 \rangle}K_2 +  M^{\langle 2 \rangle}K_1) + (t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) $

\text{ } \text{ } $+  \dfrac{1}{\Delta}\cdot (K_1K_2q^2 
 + E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})) + K_5q\Bigg\rfloor $ 

\text{ } \text{ }  \textcolor{red}{ $\rhd$ where $\epsilon = \dfrac{q}{\Delta} - \dfrac{q}{\dfrac{q}{t}} = \dfrac{q}{\left\lfloor\dfrac{q}{t}\right\rfloor} - \dfrac{q}{\dfrac{q}{t}} \approx 0$, thus we substituted $\dfrac{q}{\Delta} = \epsilon + t$}


 $ $

 $ $

$ = \Bigg\lceil\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + q\cdot (M^{\langle 1 \rangle}K_2 +  M^{\langle 2 \rangle}K_1) + (t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1)$

\text{ } \text{ } $ + \dfrac{K_1K_2q^2}{\Delta}   
 + \dfrac{E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})}{\Delta} + K_5q\Bigg\rfloor $

\text{ } \text{ }  \textcolor{red}{ $\rhd$ Now, let $\epsilon' = \dfrac{K_1K_2q^2}{\Delta} - \dfrac{K_1K_2q^2}{\dfrac{q}{t}} = \dfrac{K_1K_2q^2}{\left\lfloor\dfrac{q}{t}\right\rfloor} - \dfrac{K_1K_2q^2}{\dfrac{q}{t}} \approx 0$.}

\text{ } \text{ }  \textcolor{red}{ Thus, we will substitute $\dfrac{K_1K_2q^2}{\Delta} = \dfrac{K_1K_2q^2}{\dfrac{q}{t}} + \epsilon' = K_1K_2qt + \epsilon'$}
 
 $ $

 $ $

$ = \Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + (M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle}) + q\cdot (M^{\langle 1 \rangle}K_2 +  M^{\langle 2 \rangle}K_1) $

\text{ } \text{ } $+ (t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + K_1K_2qt + \epsilon'   
 + K_5q + \Bigg\lceil\dfrac{E^{\langle 1 \rangle} E^{\langle 2\rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i}) }{\Delta}\Bigg\rfloor $

 $ $

 $ $

$ = \Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + \epsilon'' + K_6q$


\textcolor{red}{ $\rhd$ where $K_6q = K_5q + q\cdot(M^{\langle 1 \rangle}K_2 +  M^{\langle 2 \rangle}K_1) + K_1K_2qt, $}

\textcolor{red}{$ \epsilon'' = M^{\langle 1 \rangle}E^{\langle 2 \rangle} + M^{\langle 2 \rangle}E^{\langle 1 \rangle} + (t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) + \Bigg\lceil\dfrac{E^{\langle 1 \rangle} E^{\langle 2 \rangle} + \sum\limits_{i=1}^{l} (E_i'\cdot D_{2,i})}{\Delta}\Bigg\rfloor$} 


$ $

$ $


$ = \Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle} + \epsilon'' \bmod q$


$ $

In conclusion, the ciphertext $\left(\left\lceil\dfrac{A_{\alpha+\beta}}{\Delta}\right\rfloor, \left\lceil\dfrac{B_{\alpha+\beta}}{\Delta}\right\rfloor\right) \bmod q$ successfully decrypts to $\Delta M^{\langle 1 \rangle}M^{\langle 2 \rangle}$ if $\epsilon'' < \dfrac{\Delta}{2} \approx \dfrac{q}{2t}$. 

$ $

\para{Noise Analysis:} Among the terms of $\epsilon''$, let's analyze the noise growth of the $(t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1)$ term after ciphertext-to-ciphertext multiplication. Each coefficient of $K_1$ is at most $n$, because $A^{\langle 1 \rangle}\cdot S + B^{\langle 1 \rangle} = \Delta M + E^{\langle 1 \rangle} + K_1q$, where the maximum possible coefficient value of $A^{\langle 1 \rangle}\cdot S + B^{\langle 1 \rangle}$ is $q\cdot n$. And the same is true for the coefficients of $K_2$. Therefore, after scaling down $(t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1)$ by $\Delta$ upon the final decryption stage, this term's down-scaled noise gets bound by: 

$\dfrac{1}{\Delta}\cdot(t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) \approx \dfrac{t}{q}\cdot(t + \epsilon)\cdot(E^{\langle 1 \rangle}K_2 + E^{\langle 2 \rangle}K_1) < \dfrac{nt \cdot (t + \epsilon)}{q} \cdot (E^{\langle 1 \rangle} + E^{\langle 2 \rangle})$

$ $

This implies that for correct decryption, $\dfrac{nt \cdot (t + \epsilon)}{q} \cdot (E^{\langle 1 \rangle} + E^{\langle 2 \rangle})$ has to be smaller than $0.5$. In other words, $E^{\langle 1 \rangle} + E^{\langle 2 \rangle}$ has to be smaller than $\dfrac{q}{2nt \cdot (t + \epsilon)}$. We can do noise analysis for all other terms for $\epsilon''$ in a similar manner. Importantly, upon decryption, the aggregation of all these noise terms' down-scaled values has to be smaller than $0.5$ for correct decryption. 

$ $

\para{Modulus Switch v.s. Rescaling: } 
Notice in the rescaling process, multiplying $\dfrac{1}{\Delta}$ to $A_{\alpha + \beta}$ and $B_{\alpha + \beta}$ results in two effects: (1) converts $\Delta^2 M^{\langle 1 \rangle} M^{\langle 2 \rangle}$ into $\Delta M^{\langle 1 \rangle}  M^{\langle 2 \rangle}$; (2) switches the modulus of the \textit{mod-raised} ciphertexts from $Q \rightarrow q$. 
In fact, modulus switch and rescaling are closely equivalent to each other. Modulus switch is a process of changing a ciphertext's modulus (e.g., $q \rightarrow q'$), while preserving the property that the decryption of both ciphertexts results in the same plaintext. On the other hand, rescaling refers to the process of changing the scaling factor of a plaintext within a ciphertext (e.g., $\Delta \rightarrow \Delta'$). Modulus switch inevitably changes the scaling factor of the plaintext within the target ciphertext, and rescaling also inevitably changes the modulus of the ciphertext that contains the plaintext (as shown in \autoref{subsubsec:bfv-mult-cipher-rescaling}). Therefore, these two terms can be used interchangeably. 


\subsubsection{Summary}
\label{subsubsec:bfv-mult-cipher-summary}

To put all things together, BFV's ciphertext-to-ciphertext multiplication is summarized as follows:

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsubsec:bfv-mult-cipher-summary}} BFV's Ciphertext-to-Ciphertext Multiplication}}]


Suppose we have the following two RLWE ciphertexts:

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

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

$ $

Multiplication between these two ciphertexts is performed as follows:

$ $

\begin{enumerate}

\item \textbf{\underline{\textsf{ModRaise}}}

Forcibly raise the modulus of the ciphertexts $(A^{\langle 1 \rangle}, B^{\langle 1 \rangle}) \bmod q$ and $(A^{\langle 2 \rangle}, B^{\langle 2 \rangle}) \bmod q$ to $Q$ (where $Q = q \cdot \Delta$) as follows:

$(A^{\langle 1 \rangle}, B^{\langle 1 \rangle}) \bmod Q$

$(A^{\langle 2 \rangle}, B^{\langle 2 \rangle}) \bmod Q$


$ $

\item \textbf{\underline{Multiplication}}

Compute the following polynomial multiplications in modulo $Q$: 

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

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

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


$ $

\item \textbf{\underline{Relinearization}} 


Compute the following:

$ \textsf{ct}_\alpha = (D
_1, D_0)$

$ \textsf{ct}_\beta = \bm{\langle} \textsf{Decomp}^{\beta, l}(D_2), \text{ } \textsf{RLev}_{S, \sigma}^{\beta, l}( S^2) \bm{\rangle}$.

$ \textsf{ct}_{\alpha + \beta} = \textsf{ct}_{\alpha} + \textsf{ct}_{\beta}$

$ $

Then, the following property holds: 

$\textsf{RLWE}^{-1}_{S, \sigma}\bm(\textsf{RLWE}_{S, \sigma}(\Delta^2 \cdot M^{\langle 1 \rangle} \cdot M^{\langle 2 \rangle})\bm) \approx \textsf{RLWE}^{-1}_{S, \sigma}\bm{(}\textsf{ct}_{\alpha + \beta}\bm)$

$ $




\item \textbf{\underline{Rescaling}}

Update $\textsf{ct}_{\alpha + \beta} = (A_{\alpha + \beta}, B_{\alpha + \beta}) \bmod Q$ to $\textsf{ct'}_{\alpha + \beta} = \left(\left\lceil\dfrac{A_{\alpha + \beta}}{\Delta}\right\rfloor, \left\lceil\dfrac{B_{\alpha + \beta}}{\Delta}\right\rfloor\right) \bmod q$. 

$ $

This plaintext rescaling process can be also viewed as a modulus switch of the ciphertext $\textsf{ct}_{\alpha + \beta}$ from $Q \rightarrow q$. 


$ $

\end{enumerate}

Note that after the ciphertext-to-ciphertext multiplication, the plaintext scaling factor $\Delta=\left\lfloor\dfrac{q}{t}\right\rfloor$, the ciphertext modulus $q$, and the private key $S$ stay the same as before.



\end{tcolorbox}


\para{The Purpose of \textsf{ModRaise}: } When we multiply polynomials at the second step of ciphertext-to-ciphertext multiplication (\autoref{subsubsec:bfv-mult-cipher-multiplication}), the underlying plaintext within the ciphertext temporarily grows to $\Delta^2 M^{\langle 1 \rangle} M^{\langle 2 \rangle}$, which exceeds the allowed maximum boundary $q$ for the plaintext (Summary~\ref*{subsec:bfv-enc-dec} in \autoref{subsec:bfv-enc-dec}). After this point, applying modulo-$q$ reduction to the intermediate result will irrevocably corrupt the plaintext. To avoid the corruption of the plaintext when it grows to $\Delta^2 M^{\langle 1 \rangle} M^{\langle 2 \rangle}$, we temporarily increase the ciphertext modulus from $q \rightarrow Q$, which is sufficiently large to hold $\Delta^2 M^{\langle 1 \rangle} M^{\langle 2 \rangle}$ without wrapping around the boundary of the ciphertext modulus. 

$ $

\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. 



\subsubsection{Application to TFHE's Ciphertext-to-Ciphertext Multiplication}
\label{subsubsec:bfv-mult-cipher-tfhe}


In \autoref{subsec:tfhe-mult-cipher}, we learned how TFHE performs ciphertext-to-ciphertext multiplication between LWE and GSW ciphertexts. However, this method is computationally expensive because it requires circuit bootstrapping to convert an LWE ciphertext into a GSW ciphertext. Such an overhead can be avoided if we directly apply BFV's ciphertext-to-ciphertext multiplication strategy to TFHE's LWE ciphertexts. Given two LWE ciphertexts to multiply, they hold the following relations:

$\textsf{LWE}_{\vec{s}, \sigma}(\Delta m^{\langle 1 \rangle} + e^{\langle 1 \rangle}) = (\vec{a}^{\langle 1 \rangle}, b^{\langle 1 \rangle }) \Rightarrow \,\,\, \vec{a}^{\langle 1 \rangle} \cdot \vec{s} + b^{\langle 1 \rangle} = \Delta m^{\langle 1 \rangle} + e^{\langle 1 \rangle} + k_1q$

$\textsf{LWE}_{\vec{s}, \sigma}(\Delta m^{\langle 2 \rangle} + e^{\langle 2 \rangle})  = (\vec{a}^{\langle 2 \rangle}, b^{\langle 2 \rangle}) \Rightarrow \,\,\, \vec{a}^{\langle 2 \rangle} \cdot \vec{s} + b^{\langle 2 \rangle} = \Delta m^{\langle 2 \rangle} + e^{\langle 2 \rangle} + k_2q$

$ $

Multiplying these two equations yields the following relation: 


$(\Delta m^{\langle 1 \rangle} + e^{\langle 1 \rangle} + k_1q) \cdot (\Delta m^{\langle 2 \rangle} + e^{\langle 2 \rangle} + k_2q)$ \textcolor{red}{ $\rhd \approx \Delta^2 m^{\langle 1 \rangle} m^{\langle 2 \rangle} \bmod q$ }

$ = (\vec{a}^{\langle 1 \rangle} \cdot \vec{s} + b^{\langle 1 \rangle}) \cdot (\vec{a}^{\langle 2 \rangle} \cdot \vec{s} + b^{\langle 2 \rangle})$ 

$ = b^{\langle 1 \rangle}b^{\langle 2 \rangle}  + (b^{\langle 2 \rangle}\vec{a}^{\langle 1 \rangle} + b^{\langle 1 \rangle}\vec{a}^{\langle 2 \rangle}) \cdot \vec{s} + (\vec{a}^{\langle 1 \rangle} \cdot \vec{s}) \cdot (\vec{a}^{\langle 2 \rangle} \cdot \vec{s}) $



$ = \underbrace{b^{\langle 1 \rangle}b^{\langle 2 \rangle}}_{d_0}  + \underbrace{(b^{\langle 2 \rangle}\vec{a}^{\langle 1 \rangle} + b^{\langle 1 \rangle}\vec{a}^{\langle 2 \rangle})}_{d_1} \cdot \vec{s} + \underbrace{(\vec{a}^{\langle 1 \rangle} \otimes \vec{a}^{\langle 2 \rangle})}_{\vec{d}_2} \cdot (\vec{s} \otimes \vec{s}) $  


$= d_0 + d_1\cdot \vec{s} + \vec{d}_2\cdot \vec{s}^{\otimes}$ \textcolor{red}{ $\rhd$ where $\vec{s}^{\otimes} = \vec{s} \otimes \vec{s}$}

$ $

, where $\otimes$ denotes an outer product of two vectors. For example, given two $n$-length vectors $\vec{v}$ and $\vec{u}$, $\vec{v} \otimes \vec{u}$ is equivalent to an $n^2$-length vector that concatenates the following $n$ distinct $n$-length vectors: $v_0\cdot\vec{u}, \,\, v_1\cdot\vec{u}, \,\, \cdots v_{n-1}\cdot\vec{u}$. Notice that the above relation is similar to that we derived in BFV's ciphertext-to-ciphertext multiplication. Therefore, similar to the remaining steps in BFV, we can relinearize and rescale this LWE term as follows:


\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsubsec:bfv-mult-cipher-summary}} TFHE's Ciphertext-to-Ciphertext Multiplication - Method 2}}]


Suppose we have the following two LWE ciphertexts:

$\textsf{LWE}_{\vec{s}, \sigma}(\Delta M^{\langle 1 \rangle}) = (\vec{a}^{\langle 1 \rangle}, b^{\langle 1 \rangle}) \bmod q$, \text{ } where $b^{\langle 1 \rangle} = -\vec{a}^{\langle 1 \rangle} \cdot \vec{s} + \Delta m^{\langle 1 \rangle} + e^{\langle 1 \rangle} \bmod q$

$\textsf{LWE}_{\vec{s}, \sigma}(\Delta M^{\langle 2 \rangle}) = (\vec{a}^{\langle 2 \rangle}, b^{\langle 2 \rangle}) \bmod q$, \text{ } where $b^{\langle 2 \rangle} = -\vec{a}^{\langle 2 \rangle} \cdot \vec{s} + \Delta m^{\langle 2 \rangle} + e^{\langle 2 \rangle} \bmod q$

$ $

Multiplication between these two LWE ciphertexts is performed as follows:

$ $

\begin{enumerate}

\item \textbf{\underline{\textsf{ModRaise}}}

Forcibly raise the modulus of the ciphertexts $(\vec{a}^{\langle 1 \rangle}, b^{\langle 1 \rangle}) \bmod q$ and $(\vec{a}^{\langle 2 \rangle}, b^{\langle 2 \rangle}) \bmod q$ to $Q$ (where $Q = q \cdot \Delta$) as follows:

$(\vec{a}^{\langle 1 \rangle}, b^{\langle 1 \rangle}) \bmod Q$

$(\vec{a}^{\langle 2 \rangle}, b^{\langle 2 \rangle}) \bmod Q$


$ $

\item \textbf{\underline{Multiplication}}

Compute the following polynomial multiplications in modulo $Q$: 

$d_0 = b^{\langle 1 \rangle}b^{\langle 2 \rangle} \bmod Q$

$d_1 = b^{\langle 2 \rangle}\vec{a}^{\langle 1 \rangle} +  b^{\langle 1 \rangle}\vec{a}^{\langle 2 \rangle} \bmod Q$

$\vec{d}_2 = \vec{a}^{\langle 1 \rangle} \otimes \vec{a}^{\langle 2 \rangle} \bmod Q$


$ $

\item \textbf{\underline{Relinearization}} 


Compute the following:

$ \textsf{ct}_\alpha = (d
_1, d_0)$

$ \textsf{ct}_\beta = \bm{\langle} \textsf{Decomp}^{\beta, l}(\vec{d}_2), \text{ } \textsf{Lev}_{\vec{s}, \sigma}^{\beta, l}(\vec{s}^{\otimes}) \bm{\rangle}$.

$ \textsf{ct}_{\alpha + \beta} = \textsf{ct}_{\alpha} + \textsf{ct}_{\beta}$

$ $

Then, the following property holds:

$\textsf{LWE}^{-1}_{\vec{s}, \sigma}\bm(\textsf{LWE}_{\vec{s}, \sigma}(\Delta^2 \cdot m^{\langle 1 \rangle} \cdot m^{\langle 2 \rangle})\bm) \approx \textsf{LWE}^{-1}_{\vec{s}, \sigma}\bm{(}\textsf{ct}_{\alpha + \beta}\bm)$

$ $




\item \textbf{\underline{Rescaling}}

Update $\textsf{ct}_{\alpha + \beta} = (\vec{a}_{\alpha + \beta}, b_{\alpha + \beta}) \bmod Q$ to $\textsf{ct'}_{\alpha + \beta} = \left(\left\lceil\dfrac{\vec{a}_{\alpha + \beta}}{\Delta}\right\rfloor, \left\lceil\dfrac{b_{\alpha + \beta}}{\Delta}\right\rfloor\right) \bmod q$. 

$ $

This plaintext rescaling process can be also viewed as a modulus switch of the ciphertext $\textsf{ct}_{\alpha + \beta}$ from $Q \rightarrow q$. 


$ $

\end{enumerate}

Note that after the ciphertext-to-ciphertext multiplication, the plaintext scaling factor $\Delta=\dfrac{q}{t}$, the ciphertext modulus $q$, and the private key $\vec{s}$ stay the same as before.



\end{tcolorbox}



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

BFV's key switching scheme changes an RLWE ciphertext's secret key from $S$ to $S'$. This scheme is essentially RLWE's key switching scheme with the sign of the $A\cdot S$ term flipped in the encryption and decryption formula. Specifically, this is equivalent to the alternative GLWE version's (\autoref{subsec:glwe-alternative}) key switching scheme (\autoref{sec:glwe-key-switching}) with $k = 1$ as follows:

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsec:bfv-key-switching}} BFV's Key Switching}}]
$\textsf{RLWE}_{S',\sigma}(\Delta M) = (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:bfv-rotation}


In this section, we will explain how to homomorphically rotate the elements of an input vector $\vec{v}$ after it is already encoded as a polynomial and encrypted as an RLWE ciphertext. In \autoref{subsec:coeff-rotation}, we learned how to rotate the coefficients of a polynomial. However, rotating the plaintext polynomial $M(X)$ or RLWE ciphertext polynomials $(A(X), B(X))$ does not necessarily rotate the input vector, which is the source of them. 

The key requirement of homomorphic rotation of input vector slots (i.e., input vector) is that this operation should be performed on the RLWE ciphertext such that after this operation, if we decrypt the RLWE ciphertext and decode it, the recovered input vector will be in a rotated state as we expect. We will divide this task into the following two sub-problems:

\begin{enumerate}[leftmargin=3\parindent]
\item How to indirectly rotate the input vector by updating the plaintext polynomial $M$ to $M'$?

\item How to indirectly update the plaintext polynomial $M$ to $M'$ by updating the RLWE ciphertext polynomials $(A, B)$ to $(A', B')$?
\end{enumerate}



\subsubsection{Rotating Input Vector Slots by Updating the Plaintext Polynomial}

In this task, our goal is to modify the plaintext polynomial $M(X)$ such that the first-half elements of the input vector $\vec{v}$ are shifted to the left by $h$ positions in a wrapping manner among them, and the second-half elements of $\vec{v}$ are also shifted to the left by $h$ positions in a wrapping manner among them. Specifically, if $\vec{v}$ is defined as follows:

$\vec{v} = (v_0, v_1, \cdots, v_{n-1})$

$ $

Then, we will denote the $h$-shifted vector $\vec{v}^{\langle h \rangle}$ as follows:  

$\vec{v}^{\langle h \rangle} = (\underbrace{v_h, v_{h+1}, \cdots, v_0, v_1, \cdots, v_{h-2}, v_{h-1},}_{\text{The first-half $\dfrac{n}{2}$ elements $h$-rotated to the left}} \text{ } \underbrace{v_{\frac{n}{2}+h}, v_{\frac{n}{2}+h+1}, \cdots, v_{\frac{n}{2}+h-2}, v_{\frac{n}{2}+h-1}}_{\text{The second-half $\dfrac{n}{2}$ elements $h$-rotated to the left}})$

$ $

Remember from \autoref{subsec:bfv-batch-encoding} that the BFV encoding scheme's components are as follows:

$\vec{v} = (v_0, v_1, v_2, \cdots, v_{n-1})$ \textcolor{red}{  $\rhd$ $n$-dimensional input vector}

$ $

$W =  \begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
(\omega) & (\omega^3) & (\omega^5) & \cdots & (\omega^{2n-1})\\
(\omega)^2 & (\omega^3)^2 & (\omega^5)^2 & \cdots & (\omega^{2n-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & (\omega^5)^{n-1} & \cdots & (\omega^{2n-1})^{n-1}\\
\end{bmatrix}$

$= \begin{bmatrix}
1 & 1 & \cdots & 1 & 1 & \cdots & 1 & 1\\
(\omega) & (\omega^3) & \cdots & (\omega^{\frac{n}{2} - 1}) & (\omega^{-(\frac{n}{2} - 1)}) & \cdots & (\omega^{-3}) & (\omega^{-1})\\
(\omega)^2 & (\omega^3)^2 & \cdots & (\omega^{\frac{n}{2} - 1})^2 & (\omega^{-(\frac{n}{2} - 1)})^2 & \cdots & (\omega^{-3})^2 & (\omega^{-1})^2\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(\omega)^{n-1} & (\omega^3)^{n-1} & \cdots & (\omega^{\frac{n}{2} - 1})^{n-1} & (\omega^{-(\frac{n}{2} - 1)})^{n-1} & \cdots & (\omega^{-3})^{n-1} & (\omega^{-1})^{n-1}\\
\end{bmatrix}$

, where $\omega = g^{\frac{t - 1}{2n}} \bmod t$ ($g$ is a generator of $\mathbb{Z}_t^{\times}$)

\textcolor{red}{ $\rhd$ The encoding matrix that converts $\vec{v}$ into $\vec{m}$ ( i.e., $n$ coefficients of the plaintext polynomial $M(X)$ )}
 


$ $

$\Delta\vec{m}  = n^{-1}\cdot\Delta W\cdot I_n^R\cdot\vec{v}$  

\textcolor{red}{  $\rhd$ A vector containing the  scaled $n$ integer coefficients of the plaintext polynomial}

$ $

$\Delta M = \sum\limits_{i=0}^{n-1} ( \Delta m_i  X^i)$ 

\textcolor{red}{ $\rhd$ The integer polynomial that isomorphically encodes the input vector $\vec{v}$}


$ $

We learned from \autoref{subsec:poly-vector-transformation} that decoding the polynomial $M(X)$ $\vec{v}$ is equivalent to evaluating $M(X)$ at the following $n$ distinct primitive $(\mu=2n)$-th root of unity: $\{\omega, \omega^3, \omega^5, \cdots, \omega^{2n-3}, \omega^{2n-1} \}$. Thus, the above decoding process is equivalent to the following:

$\vec{v} = \dfrac{W^T \Delta \vec{m}}{\Delta} = \bm{(}W^T_0\cdot \vec{m}, \text{ } W^T_1\cdot \vec{m}, \text{ } W^T_2\cdot \vec{m}, \text{ } \cdots, \text{ } W^T_{n-1}\cdot \vec{m}\bm{)}$  

$= \bm{(} \text{ } M(\omega), \text{ } M(\omega^3), \text{ } M(\omega^5), \cdots, M(\omega^{2n-3}), \text{ } M(\omega^{2n-1}) \text{ } \bm{)}$


$= \bm{(} \text{ } M(\omega), \text{ } M(\omega^3), \text{ } M(\omega^5), \cdots, M(\omega^{n-3}), \text{ } M(\omega^{n-1}), \text{ } M(\omega^{-(n-1)}), \text{ } M(\omega^{-(n-3)}), \cdots, M(\omega^{-3}), \text{ } M(\omega{-1}) \text{ } \bm{)}$ 


%%$\textsf{LWE}_{S, \sigma}(\Delta M) = (A, B) \in \mathcal{R}_{\langle n, q \rangle }^{2}$ \textcolor{red}{  $\rhd$ An LWE ciphertext that encrypts $\Delta M$}

%$A\cdot S + B = \Delta M + E$


$ $

Now, our next task is to modify $M(X)$ to $M'(X)$ such that decoding $M'(X)$ will give us a modified input vector $\vec{v}^{\langle h \rangle}$ that is a rotation of the first half elements of $\vec{v}$ by $h$ positions to the left (in a wrapping manner among them), and the second half elements of it also rotated by $h$ positions to the left (in a wrapping manner among them). To accomplish this rotation, we will take a 2-step solution: 

\begin{enumerate}[leftmargin=3\parindent]
\item To convert $M(X)$ into $M'(X)$, we will define the new mapping $\sigma_M$ as follows: 

$\sigma_M : (M(X), h) \in (\mathcal{R}_{\langle n, t \rangle}, \mathbb{Z}_{n}) \longrightarrow M'(X) \in \mathcal{R}_{\langle n, t \rangle}$

, where $h$ is the number of rotation positions to be applied to $\vec{v}$.
\item To decode $M'(X)$ into the rotated input vector $\vec{v}^{\langle h \rangle}$, we need to re-design our decoding scheme by modifying \textsf{Encoding\textsubscript{1}}'s (\autoref{subsubsec:bfv-encoding-1}) isomorphic mapping $\sigma : M(X) \in \mathcal{R}_{\langle n, t \rangle} \longrightarrow \vec{v} \in \mathbb{Z}^n$ 
\end{enumerate}

$ $

\para{Converting $\bm{M(X)}$ into $\bm{M'(X)}$:} Our first task is to convert $M(X)$ into $M'(X)$, which is equivalent to applying our new mapping $\sigma_M : (M(X), h) \in (\mathcal{R}_{\langle n, t \rangle}, \mathbb{Z}_{n}) \longrightarrow M'(X) \in \mathcal{R}_{\langle n, t \rangle}$, such that decoding $M'(X)$ gives a rotated input vector $\vec{v}^{\langle h \rangle}$ whose first half of the elements in $\vec{v}$ are rotated by $h$ positions to the left (in a wrapping manner among them), and the second half of the elements are also rotated by $h$ positions to the left (in a wrapping manner among them). To design $\sigma_M$ that satisfies this requirement, we will use the number $5^j$ which has the following two special properties (based on number theory):
\begin{itemize}
\item $(5^j \bmod 2n)$ and $(-5^j \bmod 2n)$ generate all odd numbers between $[0, 2n)$ for the integer $j$ where $0 \leq j < \dfrac{n}{2}$. 
\item For each integer $j$ where $0 \leq j < \dfrac{n}{2}$, $(5^j \bmod 2n) + (-5^j \bmod 2n) \equiv 0 \bmod 2n$. 
\end{itemize}
For example, suppose the modulus $2n = 16$. Then, 

\begin{multicols}{2}
\noindent $5^0 \bmod 16 = 1$
\newline $5^1 \bmod 16 = 5$
\newline $5^2 \bmod 16 = 9$
\newline $5^3 \bmod 16 = 13$
\newline $-(5)^0 \bmod 16 = 15$
\newline $-(5)^1 \bmod 16 = 11$
\newline $-(5)^2 \bmod 16 = 7$
\newline $-(5)^3 \bmod 16 = 3$
\end{multicols}


As shown above, $0 \leq j < 4$ generate all odd numbers between $[0, 16)$. Also, for each $j$ in $0 \leq j < 4$, $(5^j \bmod 16) + (-5^j \bmod 16) = 16$. 

$ $

Let's define $J(h) = 5^h \bmod 2n$, \text{ } and \text{ } $J_*(h) = -5^h \bmod 2n$. Based on $J(h)$ and $J_*(h)$, we will define the mapping $\sigma_M : M(X) \rightarrow M'(X)$ as follows:

$\sigma_{M} : M(X) \rightarrow M(X^{J(h)})$

$ $

Given a plaintext polynomial $M(X)$, in order to give its decoded version of input vector $\vec{v}$ the effect of the first half of the elements being rotated by $h$ positions to the left (in a wrapping manner) and the second half of the elements also being rotated by $h$ positions to the left (in a wrapping manner), we update the current plaintext polynomial $M(X)$ to a new polynomial $M'(X) = M(X^{J(h)}) = M(X^{5^h})$ by applying the $\sigma_M$ mapping, where $h$ is the number of positions for left rotations for the first half and second half of the elements of $\vec{v}$. 


$ $

\para{Decoding $\bm{M'(X)}$ into \boldmath$\vec{v}^{\langle h \rangle}$}: Our second task is to modify our original decoding scheme in order to successfully decode $M'(X)$ into the rotated input vector $\vec{v}^{\langle h \rangle}$. For this, we will modify our original isomorphic mapping $\sigma : M(X) \longrightarrow \vec{v}$, from:

$\sigma: M(X) \in \mathcal{R}_{\langle n, q \rangle} \longrightarrow  \bm{(}M(\omega), M(\omega^3),M(\omega^5), \cdots, M(\omega^{2n-1})\bm{)} \in \mathbb{Z}^n$ \textcolor{red}{ \text{ } \# designed in \autoref{subsec:poly-vector-transformation}}

$ $

, to the following: 

$\sigma_J: M(X) \in \mathcal{R}_{\langle n, t \rangle} \longrightarrow  \bm{(}M(\omega^{J(0)}),M(\omega^{J(1)}),M(\omega^{J(2)}), \cdots, M(\omega^{J(\frac{n}{2} - 1)}), $

\textcolor{white}{$\sigma_J: M(X) \in \mathcal{R}_{\langle n, q \rangle} \longrightarrow  \bm{(}$} $M(\omega^{J_*(0)}), \text{ } M(\omega^{J_*(1)}), \text{ } M(\omega^{J_*(2)}), \cdots, M(\omega^{J_*(\frac{n}{2} - 1}) \text{ } \bm{)} \in \mathbb{Z}^{n}$


$ $

The common aspect between $\sigma$ and $\sigma_J$ is that they both evaluate the polynomial $M(X)$ at $n$ distinct primitive $(\mu=2n)$-th roots of unity (i.e., $w^i$ for all odd $i$ between $[0,2n]$ ). In the case of the $\sigma_J$ mapping, note that $J(j) = 5^j \bmod 2n$ \text{ } and \text{ } $J_*(j) = -5^j \bmod 2n$ \text{ } for each $j$ in $0 \leq j < \dfrac{n}{2} $ \text{ }  cover all odd numbers between $[0, 2n]$. Therefore, $\omega^{J(j)}$ and $\omega^{J_*(j)}$ between $0 \leq j < \frac{n}{2}$ cover all $n$ distinct primitive $(\mu=2n)$-th roots of unity.

Meanwhile, the difference between $\sigma$ and $\sigma_J$ is the order of the output vector elements. In the $\sigma$ mapping, the order of evaluated coordinates for $M(X)$ is $\omega, \omega^3, \cdots, \omega^{2n - 1}$, whereas in the $\sigma_J$ mapping, the order of evaluated coordinates is $\omega^{J(0)}, \omega^{J(1)}, \cdots, \omega^{J(\frac{n}{2} - 1)}, \omega^{J_*(0)}, \omega^{J_*(1)}, \cdots, \omega^{J_*(\frac{n}{2} - 1)}$. We will later explain why we modified the ordering like this. 

In the original \textsf{Decoding\textsubscript{2}} process (\autoref{subsec:bfv-batch-encoding}), applying the $\sigma$ mapping to a plaintext polynomial $M(X)$ was equivalent to computing the following: 

$\vec{v}_{'} = \bm{(} \text{ } M(\omega), \text{ } M(\omega^3), \text{ } M(\omega^5), \cdots, M(\omega^{2n-3}), \text{ } M(\omega^{2n-1}) \bm{)}$ 

$ $

$ = \bm{(} \text{ } M(\omega), \text{ } M(\omega^3), \text{ } M(\omega^5), \cdots, M(\omega^{n-1}), \text{ } M(\omega^{-(n-1)}), \cdots, \text{ } M(\omega^{-3}), \text{ } M(\omega^{-1}) \text{ } \bm{)}$ 

$ $

$= \bm{(} \text{ } W^T_0\cdot \vec{m}, \text{ } W^T_1\cdot \vec{m}, \text{ } W^T_2\cdot \vec{m}, \text{ } \cdots, \text{ } W^T_{n-1}\cdot \vec{m} \text{ } \bm{)} $ 
$ $ \textcolor{red}{ $\rhd$ where $W_i^T$ is the $(i+1)$-th row of $W^T$}

$ = W^T \vec{m} $
%$= \dfrac{I_n^R}{n}\cdot \bm{(} \text{ } M(\omega), \text{ } M(\omega^3), \text{ } M(\omega^5), \cdots, M(\omega^{2n-3}), \text{ } M(\omega^{2n-1}) \text{ } )$




$ $

Similarly, the modified $\sigma_J$ mapping to the plaintext polynomial $M(X)$ is equivalent to computing the following:

$\vec{v}_{'} =  \bm{(} \text{ } 
M(\omega^{J(0)}), \text{ } M(\omega^{J(1)}), \text{ } M(\omega^{J(2)}), \cdots,  M(\omega^{J(\frac{n}{2}-1)}), \text{ } M(\omega^{J_*(0)}), \text{ } M(\omega^{J_*(1)}), \cdots,  M(\omega^{J_*(\frac{n}{2}-1)}) \text{ } \bm{)}$


$ $

$= \bm{(} \text{ } \hathat{W}^*_0\cdot \vec{m}, \text{ } \hathat{W}^*_1\cdot \vec{m}, \text{ } \hathat{W}^*_2\cdot \vec{m}, \text{ } \cdots, \text{ } \hathat{W}^*_{n-1}\cdot \vec{m} \text{ } \bm{)} $ 

$ $

$ = \hathat{W}^* \vec{m} $, where 

$ $

\noindent $\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}$

$ $

$ $

\noindent $\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 & \vdots & \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} & \cdots  & (\omega^{J_*(0)})^{n-1}
\end{bmatrix}$

$ $

$ $

From this point, we will replace $W$ in the \textsf{Encoding\textsubscript{1}} process (\autoref{subsec:bfv-batch-encoding}) by $\hathat{W}$, and $W^T$ in the \textsf{Decoding\textsubscript{2}} process by $\hathat{W}^*$. 

$ $

To demonstrate that $\hathat{W}$ is a valid encoding matrix like $W$ and $\hathat{W}^*$ is a valid decoding matrix like $W^T$, we need to prove the following 2 aspects:
\begin{itemize}[leftmargin=3\parindent]

\item \textbf{${\hathat{\bm W}}$ is a basis of the $\bm{n}$-dimensional vector space:} This is true, because $\hathat{W}$ is simply a row-wise re-ordering of $W$, which is still a basis of the $\bm{n}$-dimensional vector space.

\item \boldmath{$\hathat{W}^{*} \cdot \hathat{W} = n \cdot I_n^R$ (to satisfy Theorem~\ref*{subsec:vandermonde-euler} in \autoref{subsec:vandermonde-euler})}: This proof is split into 2 sub-proofs: 
\begin{enumerate}[leftmargin=2\parindent]
\item \boldmath{${\hathat{ W}^{ *} \cdot \hathat{ W}}$ has value $\bm{n}$ along the anti-diagonal line:} Each element along the anti-diagonal line of \boldmath$\hathat{ W}^{ *} \cdot \hathat{ W}$ is computed as $\sum\limits_{i=0}^{n-1} \omega^{2nik} = n$ where $k$ is some integer.
\item \boldmath{${\hathat{ W}^{ *} \cdot \hathat{ W}}$ has value 0 at all other coordinates:} All other elements except for the ones along the anti-diagonal lines are $\sum\limits_{i=0}^{n-1}\omega^{2i} \dfrac{\omega^n - 1}{\omega - 1} = 0$ (by Geometric Sum). 
\end{enumerate}

We provide \href{https://github.com/fhetextbook/fhe-textbook/blob/main/source%20code/bfv_j_matrix_inverse_proof.py}{\underline{the Python script}} that empirically demonstrates this. 

\end{itemize}




Therefore, $\hathat{W}^*$ and $\hathat{W}$ are valid encoding \& decoding matrices that transform $\vec{v}$ into $M(X)$. 

$ $

Now, let's think about what will be the structure of $\vec{v}^{\langle h \rangle}$ (i.e., the first-half elements of $\vec{v}$ being rotated $h$ positions to the left in a wrapping manner among them and the second-half elements of it also being rotated $h$ positions to the left in a wrapping manner among them). Remember that $\vec{v}$ is as follows:

$\vec{v} = \bm{(} \text{ } 
M(\omega^{J(0)}), \text{ } M(\omega^{J(1)}), \cdots,  M(\omega^{J(\frac{n}{2}-1)}), \text{ } 
M(\omega^{J_*(0)}), \text{ } M(\omega^{J_*(1)}),  \cdots,  M(\omega^{J_*(\frac{n}{2}-1)}) \bm{)}$


\text{ } \text{ } $= \bm{(} \text{ } \hathat{W}^*_0\cdot \vec{m}, \text{ } \hathat{W}^*_1\cdot \vec{m}, \text{ } \hathat{W}^*_2\cdot \vec{m}, \text{ } \cdots, \text{ } \hathat{W}^*_{n - 1}\cdot \vec{m} \text{ } \bm{)} $ 

$ $

Thus, the state of $\vec{v}^{\langle h \rangle}$ which is equivalent to rotating $\vec{v}$ by $h$ positions to the left for the first-half and second-half element groups will be the following: 

$\vec{v}^{\langle h \rangle} = \bm{(} \text{ } M(\omega^{J(h)}), \text{ } M(\omega^{J(h+1)}), \cdots, M(\omega^{J(\frac{n}{2}-1)}), \text{ } M(\omega^{J(0)}), \text{ }M(\omega^{J(1)}), \cdots, \text{ } M(\omega^{J(h-2)}), \text{ } M(\omega^{J(h-1)}),$

\text{ }\text{ }\text{ } $ M(\omega^{J_*(h)}), \text{ } M(\omega^{J_*(h+1)}), \cdots, M(\omega^{J_*(\frac{n}{2}-1)}), \text{ } M(\omega^{J_*(0)}), \text{ }M(\omega^{J_*(1)}), \cdots, \text{ } M(\omega^{J_*(h-2)}), \text{ } M(\omega^{J_*(h-1)}) \text{ } \bm{)}$

$ $

Notice that the above computation of $\vec{v}^{\langle h \rangle}$ is equivalent to vertically rotating the upper $\frac{n}{2}$ rows of $\hathat{W}^*$ by $h$ positions upward (in a wrapping manner among them), rotating the lower $\frac{n}{2}$ rows of $\hathat{W}^{*}$ by $h$ positions upward (in a wrapping manner among them), and multiplying the resulting matrix with $\vec{m}$. However, it is not desirable to directly modify the decoding matrix $\hathat{W}^*$ like this in practice, because then the decoding matrix loses its consistency. Therefore, instead of directly modifying $\hathat{W}^*$, we will modify $\vec{m}$ to $\vec{m}_{'}$ (i.e., modify $M(X)$ to $M'(X)$) such that the relation $\vec{v}^{\langle h \rangle} = \hathat{W}^* \cdot \vec{m}_{'}$ holds. Let's extract the upper-half rows of $\hathat{W}^*$ and denote this $\dfrac{n}{2} \times n$ matrix as $\hathat{H}_1^*$. Then, $\hathat{H}_1^*$ is equivalent to a Vandermonde matrix (Definition~\ref*{subsec:vandermonde} in \autoref{subsec:vandermonde}) in the form of $V(\omega^{J(0)}, \omega^{J(1)}, \cdots, \omega^{J(\frac{n}{2}-1)})$. Similarly, let's extract the lower-half rows of $\hathat{W}^*$ and denote this $\dfrac{n}{2} \times n$ matrix as $\hathat{H}_2^*$. Then, $\hathat{H}_2^*$ is equivalent to a Vandermonde matrix (Definition~\ref*{subsec:vandermonde} in \autoref{subsec:vandermonde}) in the form of $V(\omega^{J_*(0)}, \omega^{J_*(1)}, \cdots, \omega^{J_*(\frac{n}{2}-1)})$. 

Now, let's vertically rotate the rows of $\hathat{H}_1^*$ by $h$ positions upward and denote it as $\hathat{H}_1^{*\langle h \rangle}$; and vertically rotate the rows of $\hathat{H}_2^*$ by $h$ positions upward and denote it as $\hathat{H}_2^{*\langle h \rangle}$. And let's denote the $\dfrac{n}{2}$-dimensional vector comprising the first-half elements of $\vec{v}^{\langle h \rangle}$ as $\vec{v}_1^{\langle h \rangle}$, and the $\dfrac{n}{2}$-dimensional vector comprising the second-half elements of $\vec{v}^{\langle h \rangle}$ as $\vec{v}_2^{\langle h \rangle}$. 
Then, computing (i.e., decoding) $\vec{v}_1^{\langle h \rangle} = \hathat{H}_1^{*\langle h \rangle}\cdot \vec{m}$ is equivalent to modifying $M(X)$ to $M'(X) = M(X^{J(h)})$ (whose coefficient vector is $\vec{m}^{\langle h \rangle}$) and then computing (i.e., decoding) $\vec{v}_1^{\langle h \rangle} = \hathat{H}_1^{*}\cdot \vec{m}^{\langle h \rangle}$. This is because:

$\vec{v}_1^{\langle h \rangle} =\hathat{H}_1^{*\langle h \rangle}\cdot \vec{m}$

$ = \bm{(} \text{ } \hathat{W}^*_{h}\cdot\vec{m}, \text{ } \hathat{W}^*_{h+1}\cdot\vec{m}, \text{ } \hathat{W}^*_{h+2}\cdot\vec{m}, \cdots, \hathat{W}^*_{\frac{n}{2}-1}\cdot\vec{m}, \text{ } \hathat{W}^*_{0}\cdot\vec{m}, \text{ }\hathat{W}^*_{1}\cdot\vec{m}, \cdots, \text{ } \hathat{W}^*_{h-2}\cdot\vec{m}, \text{ } \hathat{W}^*_{h-1}\cdot\vec{m}  \bm{)}$

$ $

$= \bm{(} \text{ } M((\omega^{J(h)})^{J(0)}), \text{ } M((\omega^{J(h)})^{J(1)}), \text{ } M((\omega^{J(h)})^{J(2)}), \cdots, M((\omega^{J(h)})^{J(\frac{n}{2}-1)}) \text{ } \bm{)}$


\textcolor{red}{ $\rhd$ This is equivalent to evaluating the polynomial $M(X^{J(h)})$ at the following $\dfrac{n}{2}$ distinct $(\mu=2n)$-th roots of unity: $\omega^{J(0)}, \omega^{J(1)},  \omega^{J(2)}, \cdots, \omega^{J(\frac{n}{2} - 1)}$}

$ $

$= \bm{(} \text{ } M(\omega^{J(h)\cdot J(0)}), \text{ } M(\omega^{J(h)\cdot J(1)}), \text{ } M(\omega^{J(h)\cdot J(2)}), \cdots, M(\omega^{J(h)\cdot J(\frac{n}{2}-1)}) \text{ } \bm{)}$

$= \bm{(} \text{ } M(\omega^{5^h\cdot 5^0}), \text{ } M(\omega^{5^h\cdot 5^1}), \text{ } M(\omega^{5^h\cdot 5^2}), \cdots, M(\omega^{5^h\cdot 5^{n/2-1}}) \text{ } \bm{)}$

$= \bm{(} \text{ } M(\omega^{5^{h}}), \text{ } M(\omega^{5^{h+1}}), \text{ } M(\omega^{5^{h+2}}), \cdots, M(\omega^{5^{h+n/2-1}}) \text{ } \bm{)}$ \textcolor{red}{ $\rhd$ note that $5^{\frac{n}{2}} \bmod 2n = 1$}

$ $

$= \bm{(} \text{ } M(\omega^{J(h)}), \text{ } M(\omega^{J(h+1)}), \text{ } M(\omega^{J(h+2)}), \cdots, M(\omega^{J(\frac{n}{2}-1)}), \text{ } M(\omega^{J(0)}), \text{ }M(\omega^{J(1)}),$ 
                                    
$\cdots, \text{ } M(\omega^{J(h-2)}), \text{ } M(\omega^{J(h-1)})  \bm{)}$ 

$ $

$= \tilde{H}_1^{*}\cdot \vec{m}^{\langle h \rangle}$ \textcolor{red}{ \text{ } \# where $\vec{m}^{\langle h \rangle}$ contains the $n$ coefficients of the polynomial $M(X^{J(h)})$ }


$ $

Similarly, computing (i.e., decoding) $\vec{v}_2^{\langle h \rangle} = \hathat{H}_2^{*\langle h \rangle}\cdot \vec{m}$ is equivalent to modifying $M(X)$ to $M'(X) = M(X^{J(h)})$ (whose coefficient vector is $\vec{m}^{\langle h \rangle}$) and then computing (i.e., decoding) $\vec{v}_2^{\langle h \rangle} = \hathat{H}_2^{*}\cdot \vec{m}^{\langle h \rangle}$. This is because,

$\vec{v}_2^{\langle h \rangle} =\hathat{H}_2^{*\langle h \rangle}\cdot \vec{m}$

$ $


$ = \bm{(} \text{ } \hathat{W}^*_{\frac{n}{2} +h}\cdot\vec{m}, \text{ } \hathat{W}^*_{\frac{n}{2} + h+1}\cdot\vec{m}, \text{ } \hathat{W}^*_{\frac{n}{2} +h+2}\cdot\vec{m}, \cdots, \hathat{W}^*_{n -1}\cdot\vec{m}, \text{ } \hathat{W}^*_{\frac{n}{2}}\cdot\vec{m}, \text{ }\hathat{W}^*_{\frac{n}{2} + 1}\cdot\vec{m}, \cdots,$

\text{ }\text{ }\text{ }\text{ }$ \text{ } \hathat{W}^*_{\frac{n}{2} + h-2}\cdot\vec{m}, \text{ } \hathat{W}^*_{\frac{n}{2} + h-1}\cdot\vec{m}  \bm{)}$

$ $

$= \bm{(} \text{ } M((\omega^{J(h)})^{J_*(0)}), \text{ } M((\omega^{J(h)})^{J_*(1)}), \text{ } M((\omega^{J(h)})^{J_*(2)}), \cdots, M((\omega^{J(h)})^{J_*(\frac{n}{2}-1)}) \text{ } \bm{)}$


\textcolor{red}{ $\rhd$ This is equivalent to evaluating the polynomial $M(X^{J(h)})$ at the following $\dfrac{n}{2}$ distinct $(\mu=2n)$-th roots of unity: $\omega^{J_*(0)}, \omega^{J_*(1)},  \omega^{J_*(2)}, \cdots, \omega^{J_*(\frac{n}{2} - 1)}$}

$ $

$= \bm{(} \text{ } M(\omega^{J(h)\cdot J_*(0)}), \text{ } M(\omega^{J(h)\cdot J_*(1)}), \text{ } M(\omega^{J(h)\cdot J_*(2)}), \cdots, M(\omega^{J(h)\cdot J_*(\frac{n}{2}-1)}) \text{ } \bm{)}$

$= \bm{(} \text{ } M(\omega^{5^h\cdot -5^0}), \text{ } M(\omega^{5^h\cdot -5^1}), \text{ } M(\omega^{5^h\cdot -5^2}), \cdots, M(\omega^{5^h\cdot -5^{n/2-1}}) \text{ } \bm{)}$

$= \bm{(} \text{ } M(\omega^{-5^{h}}), \text{ } M(\omega^{-5^{h+1}}), \text{ } M(\omega^{-5^{h+2}}), \cdots, M(\omega^{-5^{h+n/2-1}}) \text{ } \bm{)}$ \textcolor{red}{ $\rhd$ note that $-(5^{\frac{n}{2}} \bmod 2n) = -1$}

$ $

$= \bm{(} \text{ } M(\omega^{J_*(h)}), \text{ } M(\omega^{J_*(h+1)}), \text{ } M(\omega^{J_*(h+2)}), \cdots, M(\omega^{J_*(\frac{n}{2}-1)}), \text{ } M(\omega^{J_*(0)}), \text{ }M(\omega^{J_*(1)}),$ 
                                    
$\cdots, \text{ } M(\omega^{J_*(h-2)}), \text{ } M(\omega^{J_*(h-1)})  \bm{)}$ 

$ $

$= \hathat{H}_2^{*}\cdot \vec{m}^{\langle h \rangle}$


$ $

The above derivations demonstrate that $\vec{v}_1^{\langle h \rangle} = \hathat{H}_1^{*}\cdot \vec{m}^{\langle h \rangle}$, and $\vec{v}_2^{\langle h \rangle} = \hathat{H}_2^{*}\cdot \vec{m}^{\langle h \rangle}$. Combining these two findings, we reach the conclusion that $\vec{v}^{\langle h \rangle} = \hathat{W}^* \cdot \vec{m}^{\langle h \rangle}$: rotating the first-half elements of the input vector $\vec{v}$ by $h$ positions to the left and the second-half elements of it by $h$ positions also to the left is equivalent to updating the plaintext polynomial $M(X)$ to $M(X^{J(h)})$ and then decoding it with the decoding matrix $\hathat{W}^*$. 



However, now a new problem is that we cannot directly update the plaintext $M(X)$ to $M(X^{J(h)})$, because $M(X)$ is encrypted as an RLWE ciphertext. Therefore, we need to instead update the RLWE ciphertext components $(A, B)$ to \textit{indirectly} by updating $M(X)$ to $M(X^{J(X)})$. We will explain this in the next subsection. 


\subsubsection{Updating the Plaintext Polynomial by Updating the Ciphertext Polynomials}

Given an RLWE ciphertext $\textsf{ct} = (A, B)$, our goal is to update $\textsf{ct} = (A, B)$ to $C^{\langle h \rangle} = (A^{\langle h \rangle}, B^{\langle h \rangle})$ such that decrypting it gives the input vector $\vec{v}^{\langle h \rangle}$. That is, the following relation should hold: 

$\textsf{RLWE}^{-1}_{S, \sigma}\bm{(} \text{ } C^{\langle h \rangle} = (A^{\langle h \rangle}, B^{\langle h \rangle}) \text{ }\bm{)} = \Delta M(X^{J(h)}) + E'$

$ $

Remember that in the RLWE cryptosystem (\autoref{sec:rlwe})'s alternative version (\autoref{subsec:glwe-alternative}), the plaintext and ciphertext pair have the following relation:

$\Delta M(X) + E(X) = A(X)\cdot S(X) + B(X) \approx \Delta M(X)$

$ $

If we apply $X = X^{J(h)}$ in the above relation, we can derive the following relation: 

$\Delta M(X^{J(h)}) + E(X^{J(h)}) = A(X^{J(h)}) \cdot S(X^{J(h)}) + B(X^{J(h)}) \approx \Delta M(X^{J(h)})$

$ $

This relation implies that if we decrypt the ciphertext $C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)}))$ with $S(X^{J(h)})$ as the secret key, then we get $\Delta M(X^{J(h)})$. Therefore, $C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)}))$ is the RLWE ciphertext we are looking for, because decrypting it and then decoding its plaintext $M(X^{J(h)})$ will give us the input vector $\vec{v}^{\langle h \rangle}$. 

We can easily convert $\textsf{ct} = (A(X), B(X))$ into $C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)}))$ by applying $X^{J(h)}$ to $X$ for each of the $A(X)$ and $B(X)$ polynomials. However, after that, notice that the decryption key of the RLWE ciphertext $C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)}))$ has been changed from $S(X)$ to $S(X^{J(h)})$. Thus, we need to additionally switch the ciphertext $C^{\langle h \rangle}$'s key from $S(X^{J(h)}) \rightarrow S(X)$, which is equivalent to converting $\textsf{RLWE}_{S(X^{J(h)}), \sigma}\bm{(} C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)})) \bm{)}$ into $\textsf{RLWE}_{S, \sigma}\bm{(} C^{\langle h \rangle} = (A(X^{J(h)}), B(X^{J(h)})) \bm{)}$. For this, we will apply the BFV key switching technique (Summary~\ref*{subsec:bfv-key-switching}) learned in \autoref{subsec:bfv-key-switching} as follows: 

$ $

\noindent $\underbrace{\textsf{RLWE}_{S(X),\sigma}\bm{(}\Delta M(X^{J(h)})\bm{)}}_{\substack{\text{the result of} \\ \text{plaintext-to-ciphertext addition}}} = \underbrace{\bm{(} \text{ } 0, B(X^{J(h)}) \text{ } \bm{)}}_{\substack{\text{the plaintext } B(X^{J(h)}) \\ \text{(trivial ciphertext)}}} + \bm{\langle} \text{ } \underbrace{\textsf{Decomp}^{\beta, l}\bm{(}A(X^{J(h)})\bm{)}, \text{ } \textsf{RLev}_{S(X), \sigma}^{\beta, l}\bm{(}S(X^{J(h)})\bm{)} \text{ } \bm{\rangle}}_{\substack{\substack{\text{an RLWE ciphertext encrypting $A(X^{J(h)}) \cdot S(X^{J(h)})$}\\ \text{which is key-switched from $S(X^{J(h)})\rightarrow S(X)$}}}}$



\subsubsection{Summary}
\label{subsubsec:bfv-rotation-summary}

We summarize the procedure of rotating the BFV input vectors as follows: 

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

To support input vector slot rotation, we update the original encoding matrix in \textsf{Encoding\textsubscript{1}} as follows: 

$ $

{\footnotesize{\noindent $\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 & \vdots & \ddots & \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} & \cdots  & (\omega^{J_*(0)})^{n-1}
\end{bmatrix}$}}

$ $

$ $


, and update the original decoding matrix in \textsf{Decoding\textsubscript{2}} as follows:

$\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}$

$ $

$ $

, where $J(h)$ is the \textit{rotation helper formula}: $J(h) = 5^h \bmod 2n$, 
\text{ } $J_*(h) = -5^h \bmod 2n$. 

$ $

Using $\hathat{W}$, the encoding is perform as: $\vec{m} = n^{-1}\cdot \hathat{W} \cdot I_n^R \cdot \vec{v}$. Using $\hathat{W}^*$, the decoding is performed as $\vec{v} = \hathat{W}^* \cdot \vec{m}$

$ $

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

$\textsf{RLWE}_{S, \sigma}(\Delta M) = (A, B)$, \text{ } $\textsf{RLev}_{S, \sigma}^{\beta, l}\bm(S(X^{J(h)})\bm)$

$ $

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 (\autoref{subsec:ckks-key-switching}) from $S(X^{J(h)})$ to $S(X)$:

$\textsf{RLWE}_{S(X),\sigma}\bm{(}\Delta M(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}


\subsubsection{Encoding Example}
\label{subsubsec:bfv-batch-encoding-ex}

%$bfv_vector = [10, 0, 5, 13]
%bfv_vector2 = [2, 4, 8, 6]


In the above example, we use the unsigned modulo representation (e.g., $[0, t-1], [0, q]$) when computing $\bmod t$ and $\bmod q$. However, the correctness of the result holds even if we use the centered modulo representation (e.g., $[-\dfrac{t}{2}, \dfrac{t}{2})$, $[-\dfrac{q}{2}, \dfrac{q}{2})$). In many actual FHE libraries, centered modulo arithmetic is often used to manage noise growth more effectively.

Suppose we have the following setup: 

$\mu = 8, \, n = \dfrac{\mu}{2} = 4, \, t = 17, \, q = 2^8 = 256, \, n^{-1} = 13, \, \Delta = \left\lfloor\dfrac{q}{t}\right\rfloor = 15$

$ $

$\mathcal{R}_{\langle 4, 17 \rangle} = \mathbb{Z}_{17}[X] / (X^4 + 1)$

$ $

The roots of $X^4 + 1 \pmod{17}$ are $X = \{2, 8, 15, 9\}$, as demonstrated as follows:

$2^4 \equiv 8^4 \equiv 15^4 \equiv 9^4 \equiv 16 \equiv -1 \bmod{17}$

$ $

Definition~\ref*{subsec:cyclotomic-def} (in \autoref{subsec:cyclotomic-def}) states that the roots of the $\mu$-th cyclotomic polynomial are the primitive $\mu$-th roots of unity. And Definition~\ref*{subsec:roots-def} (in \autoref{subsec:roots-def}) states that the order of the primitive $\mu$-th roots of unity is $\mu$. These definitions apply to both the cyclotomic polynomials over $X\in\mathbb{C}$ (complex numbers) and the cyclotomic polynomials over $X \in \mathbb{Z}_t$ (ring). 

Since $\{2, 8, 15, 9\}$ are the roots of the $(\mu=8)$-th cyclotomic polynomial $X^4 + 1$ over the ring $\mathbb{Z}_{17}$, they are also the $(\mu=8)$-th primitive roots of unity of $\mathbb{Z}_{17}$. Therefore, their order (\autoref{subsec:order-def}) is $\mu=8$ as demonstrated as follows: 

$2^8 \equiv 8^8 \equiv 15^8 \equiv 9^8 \equiv 1 \bmod 17$

$2^4 \equiv 8^4 \equiv 15^4 \equiv 9^4 \equiv 16 \not\equiv 1 \bmod 17$

$ $

Definition~\ref*{subsec:cyclotomic-def} (in \autoref{subsec:cyclotomic-def}) and Theorem~\ref*{subsec:cyclotomic-theorem} (\autoref{subsec:cyclotomic-theorem}) also state that for each primitive $\mu$-th root of unity $\omega$, $\{\omega^k\}_{\textsf{gcd}(k, \mu) = 1}$ generates all roots of the $\mu$-th cyclotomic polynomial. Notice that in the case of the $(\mu=8)$-th cyclotomic polynomial $X^4 + 1$, its roots $\{2, 8, 15, 9\}$ generate all $(\mu=8)$-th roots of unity as follows:

$\{2^1, 2^3, 2^5, 2^7\} \equiv \{8^1, 8^3, 8^5, 8^7\} \equiv \{15^1, 15^3, 15^5, 15^7\} \equiv \{9^1, 9^3, 9^5, 9^7\} \equiv \{2, 8, 15, 9\} \bmod 17$

$ $

Among $\{2, 8, 15, 9\}$ as the roots of $X^4 + 1$, let's choose $\omega = 9$ as the base root to construct the encoding matrix $\hathat{W}$ and the decoding matrix $\hathat{W}^*$ as follows: 

$\hathat{W} = \begin{bmatrix}
1 & 1 & 1 & 1\\
\omega^{J(1)} & \omega^{J(0)} & \omega^{J_*(1)} & \omega^{J_*(0)}\\
(\omega^{J(1)})^2 & (\omega^{J(0)})^2 & (\omega^{J_*(1)})^2 & (\omega^{J_*(0)})^2\\
(\omega^{J(1)})^3 & (\omega^{J(0)})^3 & (\omega^{J_*(1)})^3 & (\omega^{J_*(0)})^3\\
\end{bmatrix}$ \textcolor{red}{  $\rhd$ where $J(h) = 5^h \bmod 8$}

$ = \begin{bmatrix}
1 & 1 & 1 & 1\\
9^{5} & 9^{1} & 9^{3} & 9^{7}\\
(9^{5})^2 & (9^{1})^2 & (9^{3})^2 & (9^{7})^2\\
(9^{5})^3 & (9^{1})^3 & (9^{3})^3 & (9^{7})^3\\
\end{bmatrix} \equiv \begin{bmatrix}
1 & 1 & 1 & 1\\
8 & 9 & 15 & 2\\
13 & 13 & 4 & 4\\
2 & 15 & 9 & 8\\
\end{bmatrix} \bmod{17}$ 

$ $ 

$\hathat{W}^* = \begin{bmatrix}
1 & \omega^{J(0)} & (\omega^{J(0)})^2 & (\omega^{J(0)})^3\\
1 & \omega^{J(1)} & (\omega^{J(1)})^2 & (\omega^{J(1)})^3\\
1 & \omega^{J_*(0)} & (\omega^{J_*(0)})^2 & (\omega^{J_*(0)})^3\\
1 & \omega^{J_*(1)} & (\omega^{J_*(1)})^2 & (\omega^{J_*(1)})^3\\
\end{bmatrix} \equiv \begin{bmatrix}
1 & 9 & 13 & 15\\
1 & 8 & 13 & 2\\
1 & 2 & 4 & 8\\
1 & 15 & 4 & 9\\
\end{bmatrix}  \bmod{17}$

$ $

Notice that Theorem~\ref*{subsec:vandermonde-euler-integer-ring} (in \autoref{subsec:vandermonde-euler-integer-ring}) is demonstrated as follows:

$\hathat{W}^* \cdot \hathat{W} = \begin{bmatrix}
1 & 9 & 13 & 15\\
1 & 8 & 13 & 2\\
1 & 2 & 4 & 8\\
1 & 15 & 4 & 9\\
\end{bmatrix} \cdot \begin{bmatrix}
1 & 1 & 1 & 1\\
8 & 9 & 15 & 2\\
13 & 13 & 4 & 4\\
2 & 15 & 9 & 8\\
\end{bmatrix} = \begin{bmatrix}
0 & 0 & 0 & 4\\
0 & 0 & 4 & 0\\
0 & 4 & 0 & 0\\
4 & 0 & 0 & 0\\
\end{bmatrix} = n I_n^{R} \pmod{17}$

$ $

Now suppose that we encode the following two input vectors (i.e., input vector slots) in $\mathbb{Z}_{17}$:

$\vec{v}_1 = (10, 3, 5, 13)$

$\vec{v}_2 = (2, 4, 3, 6)$

$\vec{v}_1 + \vec{v}_2 = (10, 3, 5, 13) + (2, 4, 3, 6) \equiv (12, 7, 8, 2) \bmod 17$

$ $

These two vectors are encoded as follows:

$ $

$\vec{m}_1 = n^{-1} \hathat{W} \cdot I_n^R \cdot \vec{v} = 13 \cdot \begin{bmatrix}
1 & 1 & 1 & 1\\
8 & 9 & 15 & 2\\
13 & 13 & 4 & 4\\
2 & 15 & 9 & 8\\
\end{bmatrix} \cdot \begin{bmatrix}
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 0 & 0\\
\end{bmatrix} \cdot \begin{bmatrix}
10\\
3\\
5\\
13\\
\end{bmatrix} \equiv (12, 11, 12, 1)  \bmod 17$

$ $

$\vec{m}_2 = n^{-1} \hathat{W} \cdot I_n^R \cdot \vec{v} = 13 \cdot \begin{bmatrix}
1 & 1 & 1 & 1\\
8 & 9 & 15 & 2\\
13 & 13 & 4 & 4\\
2 & 15 & 9 & 8\\
\end{bmatrix} \cdot \begin{bmatrix}
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 0 & 0\\
\end{bmatrix} \cdot \begin{bmatrix}
2\\
4\\
3\\
6\\
\end{bmatrix} \equiv (8, 5, 14, 6) \bmod 17$

$ $

$ $

$\Delta M_1(X) = 15\cdot(12 + 11X + 12X^2 + 1X^3) = 180 + 165X + 180X^2 + 15X^3 \pmod{q}$ \textcolor{red}{  $\rhd$ where $q = 256$}

$\Delta M_2(X) = 15\cdot(8 + 5X + 14X^2 + 6X^3) = 120 + 75X + 210X^2 + 90X^3 \pmod{q}$

$\Delta M_{1+2}(X) = \Delta M_1(X) + \Delta M_2(X) = \Delta (M_1(X) + M_2(X)) = 44 + 240X + 134X^2 + 105X^3 \pmod{q}$

$M_{1+2}(X) =\left\lceil\dfrac{44 + 240X + 134X^2 + 105X^3}{15}\right\rfloor \bmod 17$

$= \left\lceil2.933 + 16X + 8.933X^2 + 7X^3\right\rfloor \bmod 17$

$3 + 16X + 9X^2 + 7X^3 \bmod 17 $

$ $


This polynomial matches the value of $\vec{m}_{1+2}$ as follows:

$\vec{m}_1 + \vec{m}_2 = (12, 11, 12, 1) + (8, 5, 14, 6) = (20, 16, 26, 7) \equiv (3, 16, 9, 7) \bmod 17$

$ $

Finally, we decode $\vec{m}_{1+2}$ as follows:



$\vec{v}_{1+2} = \hathat{W}^* \cdot \vec{m}_{1+2} = \begin{bmatrix}
1 & 9 & 13 & 15\\
1 & 8 & 13 & 2\\
1 & 2 & 4 & 8\\
1 & 15 & 4 & 9\\
\end{bmatrix} \cdot \begin{bmatrix}3\\16\\9\\7\end{bmatrix} = (12, 7, 8, 2) \bmod{17}$

$ $

This result matches the expected vector sum $\vec{v}_1 + \vec{v}_2$.




\subsubsection{Rotation Example}
\label{subsubsec:bfv-rotation-ex}

Also in the above example, we use the unsigned modulo representation (e.g., $[0, t-1], [0, q]$) when computing $\bmod t$ and $\bmod q$. However, the correctness of the result holds even if we use the centered modulo representation (e.g., $[-\dfrac{t}{2}, \dfrac{t}{2})$, $[-\dfrac{q}{2}, \dfrac{q}{2})$).

Suppose we have the following setup: 

$\mu = 16, n = \dfrac{\mu}{2} = 8, \text{ } t = 17, \text{ } q = 2^8 = 256, \text{ } n^{-1} = 15, \text{ } \Delta = 15$

$ $

$\mathcal{R}_{\langle 8, 17 \rangle} = \mathbb{Z}_{17}[X] / (X^8 + 1)$

$ $

The roots of $X^8 + 1 \pmod{17}$ are $X = \{3, 5, 6, 7, 10, 11, 12, 14\}$, as demonstrated as follows:

$3^8 \equiv 5^8 \equiv 6^8 \equiv 7^8 \equiv 10^8 \equiv 11^8 \equiv 12^8 \equiv 14^8 \equiv 16 \equiv -1 \bmod{17}$


$ $

Among $\{3, 5, 6, 7, 10, 11, 12, 14\}$ as the roots of $X^8 + 1$, let's choose $\omega = 3$ as the base root to construct the encoding matrix $\hathat{W}$ and the decoding matrix $\hathat{W}^*$ as follows: 

$\hathat{W} = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\omega^{J(3)} & \omega^{J(2)} & \omega^{J(1)} & \omega^{J(0)} & \omega^{J_*(3)} & \omega^{J_*(2)} & \omega^{J_*(1)} & \omega^{J_*(0)}\\
(\omega^{J(3)})^2 & (\omega^{J(2)})^2 & (\omega^{J(1)})^2 & (\omega^{J(0)})^2 & (\omega^{J_*(3)})^2 & (\omega^{J_*(2)})^2 & (\omega^{J_*(1)})^2 & (\omega^{J_*(0)})^2\\
(\omega^{J(3)})^3 & (\omega^{J(2)})^3 & (\omega^{J(1)})^3 & (\omega^{J(0)})^3 & (\omega^{J_*(3)})^3 & (\omega^{J_*(2)})^3 & (\omega^{J_*(1)})^3 & (\omega^{J_*(0)})^3\\
(\omega^{J(3)})^4 & (\omega^{J(2)})^4 & (\omega^{J(1)})^4 & (\omega^{J(0)})^4 & (\omega^{J_*(3)})^4 & (\omega^{J_*(2)})^4 & (\omega^{J_*(1)})^4 & (\omega^{J_*(0)})^4\\
(\omega^{J(3)})^5 & (\omega^{J(2)})^5 & (\omega^{J(1)})^5 & (\omega^{J(0)})^5 & (\omega^{J_*(3)})^5 & (\omega^{J_*(2)})^5 & (\omega^{J_*(1)})^5 & (\omega^{J_*(0)})^5\\
(\omega^{J(3)})^6 & (\omega^{J(2)})^6 & (\omega^{J(1)})^6 & (\omega^{J(0)})^6 & (\omega^{J_*(3)})^6 & (\omega^{J_*(2)})^6 & (\omega^{J_*(1)})^6 & (\omega^{J_*(0)})^6\\
(\omega^{J(3)})^7 & (\omega^{J(2)})^7 & (\omega^{J(1)})^7 & (\omega^{J(0)})^7 & (\omega^{J_*(3)})^7 & (\omega^{J_*(2)})^7 & (\omega^{J_*(1)})^7 & (\omega^{J_*(0)})^7\\
\end{bmatrix}$ 

$ \equiv \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
12&14&5&3&10&11&7&6\\
8&9&8&9&15&2&15&2\\
11&7&6&10&14&5&3&12\\
13&13&13&13&4&4&4&4\\
3&12&14&5&6&10&11&7\\
2&15&2&15&9&8&9&8\\
7&6&10&11&5&3&12&14\\
\end{bmatrix} \bmod{17}$ 

$ $ 

$\hathat{W}^* = \begin{bmatrix}
1 & \omega^{J(0)} & (\omega^{J(0)})^2 & (\omega^{J(0)})^3 & (\omega^{J(0)})^4 & (\omega^{J(0)})^5 & (\omega^{J(0)})^6 & (\omega^{J(0)})^7\\
1 & \omega^{J(1)} & (\omega^{J(1)})^2 & (\omega^{J(1)})^3 & (\omega^{J(1)})^4& (\omega^{J(1)})^5& (\omega^{J(1)})^6& (\omega^{J(1)})^7\\
1 & \omega^{J(2)} & (\omega^{J(2)})^2 & (\omega^{J(2)})^3 & (\omega^{J(2)})^4 & (\omega^{J(2)})^5 & (\omega^{J(2)})^6 & (\omega^{J(2)})^7\\
1 & \omega^{J(3)} & (\omega^{J(3)})^2 & (\omega^{J(3)})^3 & (\omega^{J(3)})^4& (\omega^{J(3)})^5& (\omega^{J(3)})^6& (\omega^{J(3)})^7\\
1 & \omega^{J_*(0)} & (\omega^{J_*(0)})^2 & (\omega^{J_*(0)})^3 & (\omega^{J_*(0)})^4 & (\omega^{J_*(0)})^5 & (\omega^{J_*(0)})^6 & (\omega^{J_*(0)})^7\\
1 & \omega^{J_*(1)} & (\omega^{J_*(1)})^2 & (\omega^{J_*(1)})^3 & (\omega^{J_*(1)})^4& (\omega^{J_*(1)})^5& (\omega^{J_*(1)})^6& (\omega^{J_*(1)})^7\\
1 & \omega^{J_*(2)} & (\omega^{J_*(2)})^2 & (\omega^{J_*(2)})^3 & (\omega^{J_*(2)})^4 & (\omega^{J_*(2)})^5 & (\omega^{J_*(2)})^6 & (\omega^{J_*(2)})^7\\
1 & \omega^{J_*(3)} & (\omega^{J_*(3)})^2 & (\omega^{J_*(3)})^3 & (\omega^{J_*(3)})^4& (\omega^{J_*(3)})^5& (\omega^{J_*(3)})^6& (\omega^{J_*(3)})^7\\
\end{bmatrix}$

$ \equiv \begin{bmatrix}
1&3&9&10&13&5&15&11\\
1&5&8&6&13&14&2&10\\
1&14&9&7&13&12&15&6\\
1&12&8&11&13&3&2&7\\
1&6&2&12&4&7&8&14\\
1&7&15&3&4&11&9&12\\
1&11&2&5&4&10&8&3\\
1&10&15&14&4&6&9&5\\
\end{bmatrix}  \bmod{17}$

$ $

$ $

Notice that Theorem~\ref*{subsec:vandermonde-euler-integer-ring} (in \autoref{subsec:vandermonde-euler-integer-ring}) is demonstrated as follows:

$\hathat{W}^* \cdot \hathat{W} = \begin{bmatrix}
1&3&9&10&13&5&15&11\\
1&5&8&6&13&14&2&10\\
1&14&9&7&13&12&15&6\\
1&12&8&11&13&3&2&7\\
1&6&2&12&4&7&8&14\\
1&7&15&3&4&11&9&12\\
1&11&2&5&4&10&8&3\\
1&10&15&14&4&6&9&5\\
\end{bmatrix} \cdot \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
12&14&5&3&10&11&7&6\\
8&9&8&9&15&2&15&2\\
11&7&6&10&14&5&3&12\\
13&13&13&13&4&4&4&4\\
3&12&14&5&6&10&11&7\\
2&15&2&15&9&8&9&8\\
7&6&10&11&5&3&12&14\\
\end{bmatrix}$

$ = \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 8\\
0 & 0 & 0 & 0 & 0 & 0 & 8 & 0\\
0 & 0 & 0 & 0 & 0 & 8 & 0 & 0\\
0 & 0 & 0 & 0 & 8 & 0 & 0 & 0\\
0 & 0 & 0 & 8 & 0 & 0 & 0 & 0\\
0 & 0 & 8 & 0 & 0 & 0 & 0 & 0\\
0 & 8 & 0 & 0 & 0 & 0 & 0 & 0\\
8 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix} = n I_n^{R} \pmod{17}$

$ $

Now suppose that we encode the following input vector (i.e., input vector slots) in $\mathbb{Z}_{17}$:

$\vec{v} = (1, 2, 3, 4, 5, 6, 7, 8)$

By rotating this vector by 3 positions to the left (i.e., the first-half slots and the second-half slots separately wrapping around within their own group), we get a new vector:

$\vec{v}_r = (4, 1, 2, 3, 8, 5, 6, 7) \bmod 17$

$ $

$\vec{v}$ is encoded as follows:

$ $

$\vec{m} = n^{-1} \hathat{W} \cdot I_n^R \cdot \vec{v} $

$= 15 \cdot  \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
12&14&5&3&10&11&7&6\\
8&9&8&9&15&2&15&2\\
11&7&6&10&14&5&3&12\\
13&13&13&13&4&4&4&4\\
3&12&14&5&6&10&11&7\\
2&15&2&15&9&8&9&8\\
7&6&10&11&5&3&12&14\\
\end{bmatrix} \cdot \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix} \cdot \begin{bmatrix}
1\\
2\\
3\\
4\\
5\\
6\\
7\\
8\\
\end{bmatrix}$

$ \equiv (13, 16, 10, 5, 9, 12, 7, 1)  \bmod 17$


$ $

$\Delta M(X) = 15\cdot(13 + 16X + 10X^2 + 5X^3 + 9X^4 + 12X^5 + 7X^6 + X^7)$


$ = 195 + 240X + 150X^2 + 75X^3 + 135X^4 + 180X^5 + 105X^6 + 15X^7 \pmod{q}$ \textcolor{red}{  $\rhd$ where $q = 256$}

$ $

This polynomial matches the value of $\Delta M(X^{J(3)})$ as follows:

$\Delta M(X^{J(3)}) = \Delta M(X^{13}) $

$= 195 + 180X - 150X^2 - 15X^3 + 135X^4 - 240X^5 - 105X^6 + 75X^7 \pmod{q}$

$ $



%Note that the coefficients of the scaled polynomials $\Delta M(X^{J(3)})$ are still within the range of the ciphertext domain $q=64$ (which must hold throughout all homomorphic computations to preserve correctness). 

Now, we decode $M(X^{J(3)})$ as follows: 

$\vec{m}_{J(3)} = \dfrac{\Delta \vec{m}_{J(3)}}{\Delta} = \dfrac{(195, 180, -150, -15, 135, -240, -105, 75)}{15} = (13, 12, -10, -1, 9, -16, -7, 5) \pmod{17}$

$ $


$\vec{v}_{J(3)} = \hathat{W}^* \cdot \vec{m}_{J(3)} = \begin{bmatrix}
1&3&9&10&13&5&15&11\\
1&5&8&6&13&14&2&10\\
1&14&9&7&13&12&15&6\\
1&12&8&11&13&3&2&7\\
1&6&2&12&4&7&8&14\\
1&7&15&3&4&11&9&12\\
1&11&2&5&4&10&8&3\\
1&10&15&14&4&6&9&5\\
\end{bmatrix} \cdot \begin{bmatrix}
13\\
12\\
-10\\
-1\\
9\\
-16\\
-7\\
5\end{bmatrix}$

$= (4, 1, 2, 3, 8, 5, 6, 7) \pmod{17}$

$= \vec{v}_r$

$ $

The decoded $\vec{v}_{J(3)}$ matches the expected rotated input vector $\vec{v}_r$.  


$ $

In practice, we do not directly update $\Delta M(X)$ to $\Delta M(X^{J(3)})$, because we would not have access to the plaintext polynomial $M(X)$ unless we have the secret key $S(X)$. Therefore, we instead update $\textsf{ct}=\bm(A(X), B(X)\bm)$ to $\textsf{ct}^{\langle h=3 \rangle}=\bm(A(X^{J(3)}), B(X^{J(3)})\bm)$, which is equivalent to homomorphically rotating the encrypted input vector slots. Then, decrypting $\textsf{ct}^{\langle h=3 \rangle}$ and decoding it would output $\vec{v}_r$.

$ $




\para{Source Code:} Examples of BFV's batch encoding and homomorphic input vector rotation can be executed by running \href{https://github.com/fhetextbook/fhe-textbook/blob/main/source%20code/bfv.py}{\underline{this Python script}} (BFV addition) and \href{https://github.com/fhetextbook/fhetextbook.github.io/blob/main/source%20code/bfv_rotation_only.py}{\underline{this one}} (BFV rotation only). 



\subsection{Application: Matrix Multiplication}
\label{subsec:bfv-matrix-multiplication}

BFV has no clean way to do a homomorphic dot product between two vectors (i.e., $\vec{v}_1 \cdot \vec{v}_2$), because the last step of a vector dot product requires summation of all slot-wise intermediate values (i.e., $v_{1,1}v_{2,1} + v_{1,2}v_{2,2} + \cdots + v_{1,n}v_{2,n}$). However, each slot in BFV's batch encoding is independent from each other, which cannot be simply added up across slots (i.e., input vector elements). Instead, we need $n$ copies of the multiplied ciphertexts and properly align their slots by many rotation operations before adding them up. Meanwhile, the homomorphic input vector slot rotation scheme can be effectively used when we homomorphically multiply a plaintext matrix with an encrypted vector. Remember that given a matrix $A$ and vector $\vec{x}$ (Definition~\ref*{subsec:matrix-arithmetic} in \autoref{subsec:matrix-arithmetic}):

$A = \begin{bmatrix}
 a_{\langle 0, 0\rangle} & a_{\langle 0, 1\rangle} & a_{\langle 0, 2\rangle} & \cdots & a_{\langle 0, n-1\rangle}\\
 a_{\langle 1, 0\rangle} & a_{\langle 1, 1\rangle} & a_{\langle 1, 2\rangle} & \cdots & a_{\langle 1, n-1\rangle} \\
 a_{\langle 2, 0\rangle} & a_{\langle 2, 1\rangle} & a_{\langle 2, 2\rangle} & \cdots & a_{\langle 2, n-1\rangle} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
 a_{\langle m-1, 0\rangle} & a_{\langle m-1, 1\rangle} & a_{\langle m-1, 2\rangle} & \cdots & a_{\langle m-1, n-1\rangle} \\
\end{bmatrix} = \begin{bmatrix} 
\vec{a}_{\langle 0, * \rangle} \\ 
\vec{a}_{\langle 1, * \rangle} \\ 
\vec{a}_{\langle 2, * \rangle} \\ 
\vdots\\
\vec{a}_{\langle m-1, * \rangle} \\ 
\end{bmatrix}, \text{ } \vec{x} = (x_0, x_1, \cdots, x_{n-1})$

$ $

The result of $A \cdot \vec{x}$ is an $m$-dimensional vector computed as:

$A \cdot \vec{x} = \Big(\vec{a}_{\langle 0, * \rangle} \cdot \vec{x}, \text{ } \vec{a}_{\langle 1, * \rangle} \cdot \vec{x}, \text{ }\cdots,\text{ } \vec{a}_{\langle m-1, * \rangle} \cdot \vec{x} \Big) = \left(\sum\limits_{i=0}^{n-1} a_{0, i} \cdot  x_i, \text{ } \sum\limits_{i=0}^{n-1}  a_{1, i} \cdot x_i, \cdots, \text{ } \sum\limits_{i=0}^{n-1} a_{m-1, i} \cdot x_i \right)$

$ $

Let's define $\rho(\vec{v}, h)$ as the rotation of $\vec{v}$ by $h$ positions to the left. And remember that the Hadamard dot product (Definition~\ref*{subsec:vector-arithmetic} in \autoref{subsec:vector-arithmetic}) is defined as slot-wise multiplication of two vectors: 

$\vec{a} \odot \vec{b} = (a_0 b_0, \text{ } a_1 b_1, \text{ } \cdots, \text{ } a_{n-1} b_{n-1})$

$ $

Let's define $n$ distinct diagonal vector $\vec{u}_i$ extracted from matrix $A$ as follows: 

$\vec{u}_i = \{a_{\langle j \bmod m, \text{ } (i + j)\bmod n \rangle}\}_{j = 0}^{n-1}$

$ $

Then, the original matrix-to-vector multiplication formula can be equivalently constructed as follows:

$A \cdot \vec{x} = \vec{u}_0 \odot \rho(\vec{x}, 0) \text{ } + \text{ } \vec{u}_1 \odot \rho(\vec{x}, 1) \text{ } + \text{ } \cdots \text{ } + \text{ } \vec{u}_{n-1} \odot \rho(\vec{x}, n-1)$

, whose computation result is equivalent to $A \cdot \vec{x}$. 
The above formula is compatible with homomorphic computation, because BFV supports Hadamard dot product between input vectors as a ciphertext-to-plaintext multiplication between their polynomial-encoded forms (\autoref{subsec:bfv-mult-plain}), and BFV also supports $\rho(\vec{v}, h)$ as homomorphic input vector slot rotation (\autoref{subsec:bfv-rotation}). After homomorphically computing the above formula, we can consider only the first $m$ (out of $n$) resulting input vector slots to store the result of $A \cdot \vec{x}$. 



\subsection{Noise Bootstrapping}
\label{subsec:bfv-bootstrapping}

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


\noindent \textbf{- Reference 2:} 
\href{https://eprint.iacr.org/2014/873.pdf}{Bootstrapping for HELib}~\cite{10.1007/s00145-020-09368-7}

\noindent \textbf{- Reference 3:} 
\href{https://arxiv.org/pdf/1906.02867}{A Note on Lower Digits Extraction Polynomial for Bootstrapping}~\cite{huo2019notelowerdigitsextraction}

\noindent \textbf{- Reference 4:} 
\href{https://eprint.iacr.org/2024/1587.pdf}{Fully Homomorphic Encryption for Cyclotomic Prime Moduli}~\cite{cryptoeprint:2024/1587}

%\noindent \textbf{- Reference 4:} 
%\href{https://s-space.snu.ac.kr/bitstream/10371/152893/1/000000155273.pdf}{Bootstrapping Methods for Homomorphic Encryption}

%\noindent \textbf{- Reference 5:} 
%\href{https://www.esat.kuleuven.be/cosic/publications/thesis-418.pdf}{Bootstrapping Algorithms for BGV and FV}

$ $

In BFV, continuous ciphertext-to-ciphertext multiplication increases the noise in a multiplicative manner, and once the noise overflows the message bits, then the message gets corrupted. Bootstrapping is a process of resetting the grown noise. 

\subsubsection{High-level Idea}
\label{subsubsec:bfv-bootstrapping-high-level}

In this subsection, we will assume the plaintext modulus $t = p$, a prime number. Although $t$ can be generalized as $t = p^r$ where $r \in \mathbb{Z}$ and $r \geq 1$ (Summary~\ref*{subsec:bfv-enc-dec} in \autoref{subsec:bfv-enc-dec}), we will explain BFV's bootstrapping assuming $t=p$ for simplicity, and then generalize $t$ as $t = p^r$ in the end. 

The core idea of the BFV bootstrapping is to homomorphically evaluate a special polynomial $G_\varepsilon(x)$, a digit extraction polynomial modulo $p^\varepsilon$ (for some positive integer $\varepsilon$), where the input to $G_\varepsilon(x)$ is a noisy plaintext value modulo $p^\varepsilon$ and the output is a noise-free plaintext value modulo $p^\varepsilon$, shifted to the right by 1 base-$p$ digit. Here, where the noise located at the least significant digits in a base-$p$ (prime) representation is zeroed out and shifted right. For example, $G_\varepsilon(3p^3 + 4p^2 + 6p + 2) = 3p^2 + 4p^1 + 6 \bmod p^\varepsilon$. Given that the noise resides in the least significant $\varepsilon-1$ digits in base-$p$ representation, we can homomorphically and recursively evaluate $G_\varepsilon(x)$ total $\varepsilon-1$ times in a row, which zeroes out and removes the least significant (base-$p$) $\varepsilon-1$ digits of input $x$. To homomorphically evaluate the noisy plaintext through $G_\varepsilon(x) \bmod p^\varepsilon$, we need to first switch the plaintext modulus from $t$ to $p^\varepsilon$, where $q \gg p^{\varepsilon} > p = t$. The larger $\varepsilon$ is, the more likely it is that the noise gets successfully zeroed out; however, the computation overhead becomes larger. If $\varepsilon$ is small, the computation gets faster, but the digit-wise distance between the noise and the plaintext decreases, potentially corrupting the plaintext during bootstrapping, because removing the most significant noise digit may also remove the least significant plaintext digit. Therefore, $\varepsilon$ should be chosen carefully. 

$ $

The technical details of the BFV bootstrapping procedure are as follows. Suppose we have an RLWE ciphertext $(A, B)  = \textsf{RLWE}_{S, \sigma}\bm(\Delta M\bm) \bmod q$, where $A\cdot S + B = \Delta M + E$, \text{ } $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$, and $t = p$ (i.e., the plaintext modulus is a prime).

\begin{enumerate}
\item \textbf{Modulus Switch (\boldmath$q \rightarrow p^\varepsilon$):} Scale down the ciphertext modulus from $(A, B) \bmod q$ to $\left(\left\lceil \dfrac{p^\varepsilon}{q}\cdot A\right\rfloor, \left\lceil \dfrac{p^\varepsilon}{q}\cdot B\right\rfloor\right) = (A', B') \bmod p^\varepsilon$, where $p^\varepsilon \ll q$. The purpose of this modulus switch is to change the plaintext modulus to $p^\varepsilon$, which is required to use the digit extraction polynomial $G_\varepsilon(x)$ (because we need to represent the input to $G_\varepsilon(x)$ as a base-$p$ number in order to interpret it as a $\bmod p^\varepsilon$ value). Notice that $\textsf{RLWE}_{S, \sigma}^{-1}\bm(\textsf{ct} = (A', B') \bm) = p^{\varepsilon-1}M + E'$, where $E' \approx \dfrac{p^\varepsilon}{q}\cdot E  + \left(\left\lfloor\dfrac{q}{p}\right\rfloor\cdot\dfrac{p^\varepsilon}{q} - p^{\varepsilon-1}\right)\cdot M$ \textcolor{red}{ $\rhd$ the modulus switch error of $E \rightarrow E'$ plus the modulus switch error of the plaintext's scaling factor $\left\lfloor\dfrac{q}{t}\right\rfloor \rightarrow p^{\varepsilon-1}$}

$ $

\item \textbf{Homomorphic Decryption:} Suppose we have the \textit{bootstrapping key} $\textsf{RLWE}_{\Delta' S, \sigma}(S) \bmod q$, which is the secret key $S$ encrypted by $S$ (itself) modulo $q$ with the plaintext scaling factor $\Delta'$. Using this \textit{encrypted} secret key, we \textit{homomorphically} decrypt $(A', B')$ as follows:

$A' \cdot \textsf{RLWE}_{S, \sigma}\bm(\Delta' S\bm) + B'$ \textcolor{red}{ $\rhd$ where $\textsf{RLWE}_{S, \sigma}(\Delta' S)$ is a modulo-$q$ ciphertext that encrypts a modulo-$p^\varepsilon$ plaintext $S$ whose scaling factor $\Delta' = \dfrac{q}{p^\varepsilon}$ }

$ $

$= \textsf{RLWE}_{S, \sigma}\bm(\Delta' (A' \cdot S)\bm) + B'  \bmod q$

$= \textsf{RLWE}_{S, \sigma}(\Delta' \cdot \bm(A'\cdot S + B')\bm) \bmod q$

$ = \textsf{RLWE}_{S, \sigma}\bm(\Delta' \cdot (p^{\varepsilon-1} M  + E' + Kp^\varepsilon)\bm) \bmod q$ \textcolor{red}{ $\rhd$ $K$ is some integer polynomials to represent the coefficient values that wrap around $p^\varepsilon$}

%$ $

%$ = \textsf{RLWE}_{S, \sigma}\bm\left(\dfrac{q}{p} M  + \dfrac{q}{p^\varepsilon} E' + Kq\bm\right) \bmod q$

%$ = \textsf{RLWE}_{S, \sigma}\bm\left(\dfrac{q}{p} M  + E'' + Kq\bm\right) \bmod q$ \textcolor{red}{ $\rhd$ where $E'' = \dfrac{q}{p^\varepsilon} E'$}

$ $

Let's see how we derived the above relation. Suppose we compute $A'\cdot S + B' \bmod p^\varepsilon$, whose output will be $p^{\varepsilon-1}M + E'$. Now, instead of using the plaintext secret key $S$, we use an encrypted secret key $\textsf{RLWE}_{S, \sigma}(\Delta' S)$, where $S$ is a plaintext modulo $p^\varepsilon$, its scaling factor $\Delta' = \left\lfloor\dfrac{q}{p^\varepsilon}\right\rfloor$, and the ciphertext encrypting $S$ is in modulo $q$. Then, the result of homomorphically computing $A'\cdot \textsf{RLWE}_{S, \sigma}(\Delta' S) + B'$ will be an encryption of $p^{\varepsilon-1}M + E' + Kp^\varepsilon$, where $Kp^\varepsilon$ stands for the wrapping-around coefficient values of the multiples of $p^\varepsilon$. %Finally, we replace $A'\cdot \textsf{RLWE}_{S, \sigma}(S)$ with $\langle \textsf{Decomp}^{\beta, l}(A'), \textsf{RLev}_{S, \sigma}^{\beta, l}(S)\rangle$, which is computationally equivalent to $A' \cdot \textsf{RLWE}_{S, \sigma}(S)$ but the noise becomes much smaller (we will explain why later in \autoref{subsubsec:bfv-bootstrapping-homomorphic-decryption}).

Notice that we did not reduce $Kp^\varepsilon$ by modulo $p^\varepsilon$ during homomorphic decryption (without modulo-$q$ reduction), because such a homomorphic modulo reduction is not directly doable. Instead, we will handle $Kp^\varepsilon$ in the later digit extraction step. 


For simplicity, we will denote $Z = p^{\varepsilon-1} M + E' \bmod p^\varepsilon$.

$ $

\item \textbf{\textsf{CoeffToSlot}:} Move the (encrypted) polynomial $Z$'s coefficients $z_0, z_i, \cdots, z_{n-1}$ to the input vector slots of an RLWE ciphertext. This is done by computing: 

$\textsf{RLWE}_{S, \sigma}(Z) \cdot n^{-1}\cdot \hathat{W}\cdot I_R^n$

, where $n^{-1}\cdot \hathat{W}\cdot I_R^n$ is the batch encoding matrix that converts input vector slot values into polynomial coefficients (Summary~\ref*{subsubsec:bfv-rotation-summary} in \autoref{subsubsec:bfv-rotation-summary}). 

$ $

\item \textbf{Digit Extraction:} We design a polynomial $G_\varepsilon(x)$ (i.e., a digit extraction polynomial) that zeros out the least significant base-$p$  digit(s) modulo $p^{\varepsilon}$. The digit extraction procedure recursively applies $G_{2} \circ G_{3} \circ \cdots \circ G_{\varepsilon-1} \circ G_\varepsilon(x)$ to the input $x$ to eliminate the least significant (base-$p$) $\varepsilon-2$ digits of input $x$ and shifts them to the right. Regarding the input $x$, we assume the noise resides in the least significant (base-$p$) $\varepsilon-2$ digits, and the message $m$ resides in the higher base-$p$ digits modulo $p^{\varepsilon}$. Therefore, digit extraction has the effect of zeroing out and deleting (i.e., shifting to the right) the least significant $\varepsilon-1$ digits of the base-$p$ representation of $p^{\varepsilon-1}m + e$. This digit extraction is performed homomorphically. Throughout the digit extraction, the scaled plaintext message with noise stored at the input vector slots of the ciphertext gets updated from $p^{\varepsilon-1} M  + E' + Kp^\varepsilon$ to $M  + K'p$. During digit extraction, we also use a special method called scaling factor re-interpretation, which conceptually increases the scaling factor $\Delta'=\left\lfloor\dfrac{q}{p^\varepsilon}\right\rfloor$ over each round of digit extraction to $\left\lfloor\dfrac{q}{p^\varepsilon-1}\right\rfloor, \left\lfloor\dfrac{q}{p^\varepsilon-2}\right\rfloor, \ldots, \left\lfloor\dfrac{q}{p}\right\rfloor$, which equivalently has the conceptual effect of dividing the scaled message and noise stored in the plaintext slots by $p$ (i.e., shift to the right by 1 base-$p$ digit) as follows: 

\textbf{Input:} $\left\lfloor\dfrac{q}{p^{\varepsilon}}\right\rfloor \cdot \left (p^{\varepsilon-1}M + E' + K p^{\varepsilon}\right )$

\textbf{Round 1:} $\left\lfloor\dfrac{q}{p^{\varepsilon - 1}}\right\rfloor \cdot \left (p^{\varepsilon-2}M + \left\lfloor\dfrac{E'}{p}\right\rfloor + K p^{\varepsilon-1}\right )$

\textbf{Round 2:} $\left\lfloor\dfrac{q}{p^{\varepsilon - 2}}\right\rfloor \cdot \left (p^{\varepsilon-3}M + \left\lfloor\dfrac{E'}{p^2}\right\rfloor + K p^{\varepsilon-2}\right )$

$\vdots$

\textbf{Round $\varepsilon-1$:} $\left\lfloor\dfrac{q}{p}\right\rfloor \cdot (M + K p)$


$ $

Importantly, the scaling factor re-interpretation does not require any actual computation; we only change the way of interpreting the ciphertext. We will cover this in more detail. later. 


$ $


\item \textbf{\textsf{SlotToCoeff}:} Homomorphically move each input vector slot's value back to the (encrypted) polynomial coefficient position. This is done by homomorphically multiplying the decoding matrix $\hathat{W}^*$ to the ciphertext (Summary~\ref*{subsubsec:bfv-rotation-summary} in \autoref{subsubsec:bfv-rotation-summary}). The final output of this step is $ = \textsf{RLWE}_{S, \sigma}\left(\left\lfloor\dfrac{q}{p}\right\rfloor M  + E^{\langle b \rangle}\right)$, where $E^{\langle \text{b} \rangle}$ is a new small noise term generated during the homomorphic operation of \textsf{CoeffToSlot}, digit extraction, and \textsf{SlotToCoeff}. The size of $E^{\langle \text{b} \rangle}$ is fixed and smaller than $E$ and $E'$. 

\end{enumerate}


Next, we will explain each step in more detail. 

\subsubsection{Modulus Switch}
\label{subsubsec:bfv-bootstrapping-modulus-switch}

The first step of the BFV bootstrapping is to do a modulus switch from $q$ to some prime power modulus $p^\varepsilon$ where $p^\varepsilon \ll q$. Before the bootstrapping, suppose the encrypted plaintext with noise is $\Delta M + E \bmod q$. Then, after the modulus switch from $q \rightarrow p^\varepsilon$, the plaintext would scale down to $p^{\varepsilon-1}M + E' \bmod p^\varepsilon$, where $E'$ roughly contains $\left\lceil\dfrac{p^\varepsilon}{q} E\right\rfloor$ plus the modulus switching noise of the plaintext's scaling factor $\Delta \rightarrow p^{\varepsilon-1}$. The goal of the BFV bootstrapping is to zero out this noise $E'$.  

\subsubsection{Homomorphic Decryption}
\label{subsubsec:bfv-bootstrapping-homomorphic-decryption}

Let's denote the modulus-switched noisy plaintext as $Z = p^{\varepsilon-1}M + E' \bmod p^\varepsilon$. We further denote polynomial $Z$'s each degree term's coefficient $z_i$ as base-$p$ number as follows: 

$z_i = z_{i, \varepsilon-1}p^{\varepsilon-1} + z_{i, \varepsilon-2}p^{\varepsilon-2} + \cdots + z_{i,1}p + z_{i,0} \bmod p^\varepsilon$

$ $

Then, $z_i \bmod p^\varepsilon$ is a base-$p$ number comprising $\varepsilon$ digits: $\{z_{i,\varepsilon-1}, z_{i,\varepsilon-2}, \cdots, z_{i,0}\}$


We assume that the highest base-$p$ digit index for the noise is $\varepsilon-2$, which is equivalent to the noise budget, and the pure plaintext portion solely resides at the base-$p$ digit index $\varepsilon-1$ (i.e., the most significant base-$p$ digit in modulo $p^\varepsilon$). Given this assumption, we extract the noise-free plaintext by computing the following:

$\left\lceil \dfrac{z_i}{p^{\varepsilon-1}} \right\rfloor \bmod p = z_{i,\varepsilon-1}$ \textcolor{red}{ $\rhd$ where the noise is assumed to be smaller than $\dfrac{p^{\varepsilon-1}}{2}$}

The above formula is equivalent to shifting the base-$p$ number $z_i$ by $\varepsilon-1$ digits to the right (and rounding the decimal value). However, remember that we don't have direct access to polynomial $Z = p^{\varepsilon-1}M + E' \bmod p^\varepsilon$ unless we have the secret key $S$ to decrypt the ciphertext storing the plaintext. Instead, we can only derive $Z$ as an encrypted form. Specifically, we can \textit{homomorphically} decrypt the modulus-switched ciphertext $(A', B')$ by using the \textit{encrypted} secret key $\textsf{RLWE}_{S, \sigma}(\Delta' S)$ as a \textit{bootstrapping key}. For this ciphertext $\textsf{RLWE}_{S, \sigma}(\Delta' S)$, the plaintext modulus is $p^\varepsilon$, the plaintext scaling factor is $\Delta' = \dfrac{q}{p^\varepsilon}$, and the ciphertext modulus is $q$. With this encrypted secret key $S$, we homomorphically decrypt the encrypted $Z$ as follows: 


$\left(\left\lceil \dfrac{p^\varepsilon}{q}\cdot A\right\rfloor, \left\lceil \dfrac{p^\varepsilon}{q}\cdot B\right\rfloor\right) = (A', B') \bmod p^\varepsilon$ 

$ $

$A' \cdot \textsf{RLWE}_{S, \sigma}\bm(\Delta' S\bm) + B' \bmod q$


$= \textsf{RLWE}_{S, \sigma}\bm(\Delta' (A' \cdot S)\bm) + B' \bmod q$

$= \textsf{RLWE}_{S, \sigma}(\Delta' \cdot \bm(A'\cdot S + B')\bm) \bmod q$

$ = \textsf{RLWE}_{S, \sigma}\bm(\Delta' \cdot (p^{\varepsilon-1} M  + E' + Kp^\varepsilon)\bm) \bmod q$ \textcolor{red}{ $\rhd$ $K$ is some integer polynomials to represent the coefficient values that wrap around modulo $p^\varepsilon$ as multiples of $p^\varepsilon$}

$ $

$ = \textsf{RLWE}_{S, \sigma}\bm(\Delta' Z\bm) \bmod q$

$ $

During this homomorphic decryption, we did not reduce the plaintext result by modulo $p^\varepsilon$, because the homomorphic decryption is a ciphertext-to-plaintext multiplication and addition done in the ciphertext modulus $q$ (not $p^{\varepsilon}$) by using $A'$ and $B'$ as plaintexts (with the plaintext modulus $p^e$) and $\textsf{RLWE}_{S, \sigma}(\Delta' S)$ as a ciphertext (with the ciphertext modulus $q$). This is why the wrapping term $Kp^\varepsilon$ is preserved in the plaintext after the homomorphic decryption-- we will handle this term at the later stage of bootstrapping. Also, notice that the computation of $A'\cdot \textsf{RLWE}_{S, \sigma}(\Delta' S)$ would not generate much noise. This is because $A'$ is a plaintext modulo $p^\varepsilon$, and thus the new noise generated by ciphertext-to-plaintext multiplication is $A' \cdot E_s$ (where $E_s$ is the encryption noise of $\textsf{RLWE}_{S, \sigma}(\Delta' S)$). Since the ciphertext modulus $q \gg p^\varepsilon$, $q \gg A' \cdot E_s$. 

Once we have derived $\textsf{RLWE}_{S, \sigma}\bm(\Delta' Z\bm)$, our next step is to remove the noise in the lower $\varepsilon-1$ digits (in terms of base-$p$ representation) of each $z_i$ for $0 \leq i \leq n - 1$. This is equivalent to transforming noisy $\textsf{RLWE}_{S, \sigma}(\Delta' Z) = \textsf{RLWE}_{S, \sigma}\bm(\Delta' \cdot (p^{\varepsilon-1} M  + E' + Kp^\varepsilon)\bm)$ into noise-free $\textsf{RLWE}_{S, \sigma}\bm (\Delta M)\bm )$ where $\Delta = \dfrac{q}{p}$. BFV's solution to do this is to design a $p$-degree polynomial function which computes the same logical result as $\left\lceil \dfrac{z_i}{p^{\varepsilon-1}} \right\rfloor \bmod p$. We will later explain how to design this polynomial by using the digit extraction polynomial $G_\varepsilon(x)$ (\autoref{subsubsec:bfv-bootstrapping-digit-extraction}). 


However, in order to \textit{homomorphically} evaluate this polynomial at each coefficient $z_i$ given the ciphertext $\textsf{RLWE}_{S, \sigma}(\Delta' Z)$, we need to move polynomial $Z$'s each coefficient $z_i$ to the input vector slots of an RLWE ciphertext. This is because BFV supports homomorphic batched $(+, \cdot)$ operations based on input vector slots of ciphertexts as operands. Therefore, we need to evaluate the noise-removing polynomial $G_\varepsilon(x)$ based on the values stored in the input vector slots of a ciphertext. 

In the next sub-section, we will explain the \textsf{CoeffToSlot} procedure, a process of moving polynomial coefficients into input vector slots of a ciphertext \textit{homomorphically}. 

\subsubsection{\textsf{CoeffToSlot} and \textsf{SlotToCoeff}}
\label{subsubsec:bfv-bootstrapping-coefftoslot}

The goal of the \textsf{CoeffToSlot} step is to homomorphically move polynomial $Z$'s coefficients $z_i$ to input vector slots. 


In Summary~\ref*{subsubsec:bfv-rotation-summary} (in \autoref{subsubsec:bfv-rotation-summary}), we learned that the encoding formula for converting a vector of input slots $\vec{v}$ into a vector of polynomial coefficients $\vec{m}$ is: $\vec{m} = n^{-1}\cdot\hathat{W} \cdot I_n^R \cdot \vec{v}$, where $\hathat{W}$ is a basis of the $n$-dimensional vector space crafted as follows: 

$\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 & \vdots & \ddots & \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} & \cdots  & (\omega^{J_*(0)})^{n-1}
\end{bmatrix}$

$ $

\textcolor{red}{ $\rhd$ where the rotation helper function $J(h) = 5^h \bmod 2n$}

$ $

Therefore, given the input ciphertext $\textsf{ct} = \textsf{RLWE}_{S, \sigma}\bm(\Delta' Z\bm) \bmod q$, we can understand its input vector slots as storing some values such that multiplying $n^{-1}\cdot\hathat{W} \cdot I_n^R$ to each of them turns them into a coefficient $z_i$ of polynomial $Z$. This implies that if we \textit{homomorphically} multiply $n^{-1}\cdot\hathat{W} \cdot I_n^R$ to the input vector slots of $\textsf{RLWE}_{S, \sigma}\bm(\Delta' Z\bm)$, then the resulting ciphertext's $n$-dimensional input vector slots will contain the $n$ coefficients of $Z$, which is equivalent to moving the coefficients of $Z$ to the input vector slots. Therefore, the \textsf{CoeffToSlot} step is equivalent to homomorphically computing $n^{-1}\cdot\hathat{W} \cdot I_n^R \cdot \textsf{RLWE}_{S, \sigma}\bm(\Delta' Z\bm)$. We can homomorphically compute matrix-vector multiplication by using the technique explained in \autoref{subsec:bfv-matrix-multiplication}.

After the \textsf{CoeffToSlot} step, we can homomorphically eliminate the noise in the lower (base-$p$) $\varepsilon-1$ digits of each $z_i$ by homomorphically evaluating the noise-removing polynomial (to be explained in the next subsection).  

After we get noise-free coefficients of $Z$, we need to move them back from the input vector slots to their original coefficient positions. This step is called \textsf{SlotToCoeff}, which is an exact inverse procedure of \textsf{CoeffToSlot}. We also learned in Summary~\ref*{subsubsec:bfv-rotation-summary} (in \autoref{subsubsec:bfv-rotation-summary}) that the inverse matrix of $n^{-1}\cdot\hathat{W} \cdot I_n^R$ is $\hathat{W}^*$, 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}$

Therefore, the \textsf{SlotToCoeff} step is equivalent to homomorphically multiplying $\hathat{W}^*$ to the output of the noise-eliminating polynomial evaluation.  

In the next subsection, we will learn how to design the core algorithm of BFV, the noise elimination polynomial, based on the digit extraction polynomial $G_\varepsilon(x)$. 


\subsubsection{Digit Extraction}
\label{subsubsec:bfv-bootstrapping-digit-extraction}


Remember that we defined polynomial $Z$ as the scaled noisy plaintext: $Z = p^{\varepsilon-1}M + E' + Kp^\varepsilon \equiv p^{\varepsilon-1}M + E' \bmod p^\varepsilon$, and each $z_i$ is the $i$-th coefficient of $Z$ (where $0 \leq i \leq n -1$). The goal of the digit extraction step is to homomorphically zero out and delete (i.e., shift to the right) the lower (base-$p$) $\varepsilon-1$  digits of each $z_i$, where the noise resides.%, and shift the resulting number by 1 digit to the right.  

First, we always think of $z_i$ as a base-$p$ representation (since this is a modulo-$p^\varepsilon$ value) as follows:

$z_i = z_{i, \varepsilon-1}p^{\varepsilon-1} + z_{i, \varepsilon-2}p^{\varepsilon-2} + \cdots + z_{i, 2}p^2 + z_{i, 1}p + z_{i, 0} \bmod p^\varepsilon$

$ $

Next, we define a new notation that denotes $z_i$ in a different way as follows: 

$z_i = d_0 + d_*p^{\varepsilon'}$

, where $d_0 \in \mathbb{Z}_p$, and $d_* \in \mathbb{Z}$, and $\varepsilon'$ is $z_i$'s least significant base-$p$ digit index whose value is non-zero after digit index 0. Therefore, each $z_i \in \mathbb{Z}_{p^\varepsilon}$ is mapped to a unique set of $(d_0, d_*, \varepsilon')$. 


Next, we define a \textit{lifting} polynomial $F_{\varepsilon'}$ in terms of $z_i$ and its associated $(d_0, d_*, \varepsilon')$ as follows:

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

%, where $F_{\varepsilon'}(z_i)$ satisfies the above relation for all $\varepsilon'$ values such that $1 \leq \varepsilon' \leq e - 1$. 
Verbally speaking, $F_{\varepsilon'}(z_i)$ processes $z_i$ in such a way that it keeps $z_{i,0}$ (i.e., $z_{i}$'s value at the base-$p$ digit index 0) the same as before, then finds the next least significant base-$p$ digit whose value is non-zero (whose digit index is denoted as $\varepsilon'$) and zeros it, during which the subsequent higher significant base-$p$ digits may be updated to arbitrary values (i.e., the function doesn't care about those values whose base-$p$ digit index is higher than $\varepsilon'$ because they fall outside the modulo $p^{\varepsilon' + 1}$ range). 

We will show an example of how $z_i$ is updated if it is evaluated by the $F_{\varepsilon'}$ function recursively a total of $\varepsilon-1$ times in a row as follows:

$\underbrace{F_{\varepsilon-1} \cdots F_{3} \circ F_{2} \circ  F_{1}}_{\varepsilon-1 \text{ times}}(z_i)$

$ $

\para{1st Recursion:} $F_{1}(z_i) = c_{i,\varepsilon-1}p^{\varepsilon-1} + c_{i,\varepsilon-2}p^{\varepsilon-2} + \cdots + c_{i, 2}p^2 + 0p + z_{i, 0} \bmod p^\varepsilon$ 

\textcolor{red}{ $\rhd$ $F_{1}(z_i) \equiv z_{i,0} \bmod p^2$}

$ $

\para{2nd Recursion:} $F_{2} \circ F_{1}(z_i) = c'_{i,\varepsilon-1}p^{\varepsilon-1} + c'_{i,\varepsilon-2}p^{\varepsilon-2} + \cdots + 0p^2 + 0p + z_{i, 0} \bmod p^\varepsilon$  

\textcolor{red}{ $\rhd$ $F_{1} \circ F_{2}(z_i) \equiv z_{i,0} \bmod p^3$} 

$ $

\para{3rd Recursion:} $F_{3} \circ F_{2} \circ F_{1}(z_i) = c''_{i,\varepsilon-1}p^{\varepsilon-1} + c''_{i,\varepsilon-2}p^{\varepsilon-2} + \cdots + 0p^3 + 0p^2 + 0p + z_{i, 0} \bmod p^\varepsilon$  

\textcolor{red}{ $\rhd$ $F_{3} \circ F_{2} \circ F_{1}(z_i) \equiv z_{i,0} \bmod p^4$} 

$\vdots$

\para{$\bm{(\varepsilon-1)}$-th Recursion:} $\underbrace{F_{\varepsilon-1}  \circ \cdots \circ F_{3} \circ F_{2} \circ F_{1}}_{\varepsilon-1 \text{ times}}(z_i) = 0p^{\varepsilon-1} + 0p^{\varepsilon-2} + \cdots + 0p^2 + 0p + z_{i, 0} \bmod p^\varepsilon$ 

\textcolor{red}{ $\rhd$ $F_{\varepsilon-1} \cdots F_{3} \circ F_{2} \circ F_{1}(z_i) \equiv z_{i,0} \bmod p^\varepsilon$} 

$ $



In the above recursive computation, notice that the order of using function $F_{\varepsilon'}$ is specifically $F_{1} \rightarrow F_{2} \rightarrow F_{3} \rightarrow \cdots \rightarrow F_{\varepsilon -1}$. We choose this specific order because we assume that for the initial input $z_i$, we do not know its associated $\varepsilon'$ value (i.e., the least significant base-$p$ digit index whose value is non-zero after digit index 0). If we choose the order $F_{1} \rightarrow F_{2} \rightarrow F_{3} \rightarrow \cdots \rightarrow F_{\varepsilon -1}$, then regardless of the value of $z_i$, we obtain the universal guaranty that the final output will be $z_{i,0} \bmod p^\varepsilon$ (i.e., the value of the base-$p$ digit index 0).

$ $

Now, we define the digit extraction function $G_{\varepsilon, v}(z_i)$ as follows:

$G_{\varepsilon}(z_i) = \left\lfloor\dfrac{z_i}{p}\right\rfloor_p = (z_i - (\underbrace{F_{\varepsilon-1}  \circ F_{\varepsilon-2}  \circ F_{\varepsilon-3}  \cdots \circ F_{3} \cdots \circ F_{2}  \cdots \circ F_{1}}_{\varepsilon - 1 \text{ times}}(z_i)) \cdot |p^{-1}|_{q} $


, where $\left\lfloor\right\rfloor_p$ denotes division by $p$ and rounding down to the nearest multiple of $p$. Verbally speaking, $G_{\varepsilon, v}(z_i)$ is equivalent to zeroing out the least significant base-$p$ digit of $z_i$ and then shifting to the right by 1 base-$p$ digit. The shifting is done by inverse $p$ multiplication (i.e., $|p^{-1}|_{q}$). Notice that the last base-$p$ digit of $z_i - (F_{\varepsilon-1}  \circ F_{\varepsilon-2}  \circ F_{\varepsilon-3}  \cdots \circ F_{1}(z_i))$ is 0, which is exactly divisible by $p$. Thus, multiplying by the inverse $p$ has the effect of exact division (i.e., shifting the whole base-$p$ representation by 1 digit to the right). The reason why the inverse $p$ is in modulo $q$ is that we are currently under the BFV ciphertext relation: $\textsf{CoeffToSlot}\bm((A', B')\bm) = (A^{\langle c\rightarrow s \rangle}, B^{\langle c\rightarrow s \rangle}) \bmod q$, whose plaintext slots store the coefficients of $\Delta' \cdot (p^{\varepsilon - 1}M + E' + K^{\langle 1 \rangle}p^{\varepsilon}) \bmod q$. Upon homomorphically computing $(z_i - (F_{\varepsilon-1}  \circ F_{\varepsilon-2}  \circ F_{\varepsilon-3}  \cdots \circ F_{3} \cdots \circ F_{2}  \cdots \circ F_{1})$ as part of the 1st round of digit extraction, the ciphertext is updated to $(A^{\langle g_1 \rangle}, B^{\langle g_1 \rangle}) \bmod q$, whose plaintext slots store the coefficients of $\Delta' \cdot (p^{\varepsilon - 1}M + \lfloor E' \rfloor_p + K^{\langle 1 \rangle}p^{\varepsilon}) \bmod q$, where $\lfloor E' \rfloor_p$ is equivalent to rounding $E'$ down to the nearest multiple of $p$. At this point (i.e., just before inverse-$p$ multiplication in the first round), the ciphertext holds the following relation:

$A^{\langle g_1 \rangle}\cdot S  + B^{\langle g_1 \rangle} = \Delta' \cdot (p^{\varepsilon - 1}M + \left\lfloor{E'}\right\rfloor_p + K^{\langle 1 \rangle}p^{\varepsilon}) + E^{\langle g_1 \rangle} \bmod q$


$ $

, where $E^{\langle g_1 \rangle}$ is the combined noise of the \textsf{SlotToCoeff} step and the first part of the 1st round of digit extraction. We could consider multiplying $|p^{-1}|_q$ to both sides of the relation to scale down $p^{\varepsilon - 1}M, \left\lfloor{E'}\right\rfloor_p,$ and $K^{\langle 1 \rangle}p^{\varepsilon}$ by $p$. However, this causes a noise explosion problem, because this scaling will be also applied to the $E^{\langle g_1 \rangle}$ term, and $|p^{-1}|_qE^{\langle g_1 \rangle}$ is a huge value. To selectively apply the inverse-$p$ multiplication only to those terms of interest, we use the scaling factor re-interpretation technique. 

$ $


\para{Scaling Factor Re-interpretation:} Although we previously explained that  $G_{\varepsilon}$ involves the multiplication by $|p^{-1}|_{q}$, technically, we skip this multiplication and instead conceptually re-interpret the scaling factor $\Delta'$ as $\left\lfloor\dfrac{q}{p^\varepsilon}\right\rfloor \rightarrow \left\lfloor\dfrac{q}{p^\varepsilon-1}\right\rfloor \rightarrow \left\lfloor\dfrac{q}{p^\varepsilon-2}\right\rfloor \rightarrow \cdots, \left\lfloor\dfrac{q}{p}\right\rfloor$ across $\varepsilon-1$ rounds of digit extraction. During this re-interpretation, each step's $p$ being decreased in the denominator of the scaling factor is conceptually placed back into the bracket. Applying the re-interpretation of the scaling factor, the digit extraction procedure (without explicit multiplication by $|p^{-1}|_q$ at each round) is performed as follows:


\textbf{Input:} $\left\lfloor\dfrac{q}{p^{\varepsilon}}\right\rfloor \cdot (p^{\varepsilon - 1}M + E' + Kp^{\varepsilon}) \bmod q$

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

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

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

$\vdots$

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



$ $



$ $


Note that the scaling factor re-interpretation does not involve any actual computation, but only changes our way of interpreting the scaling factor. Notice that at the end of the final round, the plaintext scaling factor becomes $\left\lfloor\dfrac{q}{p}\right\rfloor$, which is the desired plaintext scaling factor for standard BFV ciphertexts. Therefore, the scaling factor re-interpretation has three benefits: (1) we skip explicit multiplication by $|p^{-1}|_q$ at each round; (2) we prevent noise explosion; (3) at the end of all rounds, the plaintext scaling factor becomes the desired value for standard BFV ciphertexts, gracefully completing the bootstrapping procedure. 

Meanwhile, there are two important points to be aware of. First, each $i$-th round of scaling factor re-interpretation creates a small drift error in the scaling factor due to the difference $\epsilon_i = p^{-1}\cdot \left\lfloor\dfrac{q}{p^{\varepsilon - i}}\right\rfloor - \left\lfloor\dfrac{q}{p^{\varepsilon - i + 1}}\right\rfloor$, where $0 \leq \epsilon_{i} < p$. Therefore, an additional drift error $E_i^{\langle \text{re} \rangle}$ is created at each $i$-th round, which is small enough to be bounded by: 

$E_i^{\langle \text{re} \rangle} \leq \epsilon_i\cdot (p^{\varepsilon - i-1}M + \left\lfloor\dfrac{E'}{p^{i}}\right\rfloor + K^{\langle i \rangle} p^{\varepsilon - i}) < p^{\varepsilon-1}M + \left\lfloor\dfrac{E'}{p}\right\rfloor + K^{\langle i \rangle}p^{\varepsilon + 1} \ll \left\lfloor\dfrac{q}{p^{\varepsilon}}\right\rfloor$

$ $

Second, at each $i$-th round of digit extraction, the plaintext operands used for ciphertext-to-plaintext homomorphic operations should encode their values with the specific scaling factor interpreted at that round: $\Delta_i' = \left\lfloor\dfrac{q}{p^{\varepsilon-i+1}}\right\rfloor$. 

$ $

Now, our final remaining task is to design the actual \textit{lifting} polynomial $F_{\varepsilon'}(z_i)$ that implements $G_{\varepsilon}$.  

$ $

\para{Designing \boldmath$F_{\varepsilon'}(z_i)$:} We will derive $F_{\varepsilon'}(z_i)$ based on the following steps. 

\begin{enumerate}
\item \textbf{\textit{Claim:}} $z_i^{p} \equiv z_{i,0} \bmod p$ 

\begin{proof}
It's true that $z_i \equiv z_{i,0} \bmod p$. Fermat's Little Theorem states $a^{p} \equiv a \bmod p$ for all $a \in \mathbb{Z}_p$ and prime $p$. Therefore, $z_i \equiv z_{i,0} \equiv z_{i,0}^{p} \equiv z^{p} \bmod p$.
\end{proof}

\item \textbf{\textit{Claim:}} $z_i^p \equiv z_{i, 0}^p \bmod p^{\varepsilon'+1}$ 

\begin{myproof}
$(z_{i,0} + kp^{\varepsilon'})^p \bmod p^{\varepsilon'+1}= \sum\limits_{j=0}^{p}  \binom{p}{j}\cdot  z_{i,0}^{j} \cdot (kp^{\varepsilon'})^{p-j} \bmod p^{\varepsilon'+1}$ \textcolor{red}{ $\rhd$ binomial expansion formula}

$ \equiv z_{i,0}^{p} \bmod p^{\varepsilon' + 1}$ \textcolor{red}{ $\rhd$ all terms where $j < p$ are $0 \bmod p^{\varepsilon' + 1}$}
\end{myproof}

$ $

\item \textbf{\textit{Claim:}} Given $p$ and $\varepsilon'$ are fixed, there exists $\varepsilon'+1$ polynomials $f_0, f_1, f_2, \cdots, f_{\varepsilon'}$ (where each polynomial is at most $p-1$ degrees) such that any $z_i$ (i.e., any number whose base-$p$ representation has 0s between the base-$p$ digit index greater than 0 and smaller than $\varepsilon'$) can be expressed as the following formula:

$z_i^p \equiv \sum\limits_{j=0}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$ 



\begin{myproof}
$z_i^p \bmod p^{\varepsilon'+1}$ can be expressed as a base-$p$ number as follows:

$z_i^p \bmod p^{\varepsilon'+1} = c_0 + c_1p + c_2p^2 + \cdots + c_{\varepsilon'}p^{\varepsilon'}$

$ $

Based on step 3's claim ($z_i^p \equiv z_{i, 0}^p \bmod p^{\varepsilon'+1}$), we know that the value of $z_i^p \bmod p^{\varepsilon' + 1}$ depends only on $z_{i,0}$ (given $p$ and $\varepsilon'$ are fixed). Therefore, we can imagine that there exists some function $f(z_{i,0})$ whose input is $z_{i,0} \in [0, p-1]$ and the output is $z_i^p \in [0, p^{\varepsilon'+1} - 1]$. Alternatively, we can imagine that there exist $\varepsilon'+1$ different functions $f_0, f_1, \cdots, f_{\varepsilon'}$ such that each $f_j$ is a polynomial whose input is $z_{i,0} \in [0, p-1]$ and the output is $c_i \in [0, p-1]$, and $z_i^p \equiv \sum\limits_{j=0}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$. In this case, the input and output domain of each polynomial $f_j$ is $[0, p - 1]$. Therefore, we can design each $f_j$ as a $(p-1)$-degree polynomial and derive each $f_j$ based on polynomial interpolation (\autoref{sec:polynomial-interpolation}) by using $p$ coordinate values. 

Note that whenever we increase $\varepsilon'$ to $\varepsilon' + 1$, we add a new polynomial $f_{\varepsilon' + 1}$. However, the previous polynomials $f_0, f_1, \cdots, f_{\varepsilon'}$ stay the same as before, because increasing $\varepsilon'$ by 1 only adds a new base-$p$ constant $c_{\varepsilon' + 1}$ for the highest base-$p$ digit, while keeping the lower-digit constants $c_0, c_1, \cdots, c_{\varepsilon'}$ the same as before. Therefore, the polynomials $f_0, f_1, \cdots, f_{\varepsilon'}$, each of which computes  $c_0, c_1, \cdots, c_{\varepsilon'}$, also stay the same as before. 

\end{myproof}

\item \textbf{\textit{Claim:}} The formula in step 4's claim can be further concretized as follows:

$z_i^p \equiv z_{i,0} + \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$

\begin{myproof}
According to step 2's claim ($z_i^{p} \equiv z_{i,0} \bmod p$), we know that the following base-$p$ representation of $z_i^p$:

$z_i^p \equiv c_0 + c_1p + c_2p^2 + \cdots + c_{\varepsilon'}p^{\varepsilon'} \bmod p^{\varepsilon'+1} $

$ $

will be the following:

$z_i^p \equiv z_{i,0} + c_1p + c_2p^2 + \cdots + c_{\varepsilon'}p^{\varepsilon'} \bmod p^{\varepsilon'+1} $

$ $

, since step 2's claim implies that the least significant base-$p$ digit of $z_i^p$ in the base-$p$ representation is always $z_{i,0}$. Thus, the formula in step 4's claim:

$z_i^p \equiv \sum\limits_{j=0}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$

$ $

can be further concretized as follows:

$ $

$z_i^p \equiv z_{i,0} + \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$

\end{myproof}

\item \textbf{\textit{Claim:}} $z_i^p - \sum\limits_{j=1}^{\varepsilon'}f_j(z_i)\cdot p^j \equiv z_{i,0} \bmod p^{\varepsilon'+1}$

\begin{myproof}

\item Remember that in step 1, we defined $z_i$ as: $z_i = z_{i,0} + \sum\limits_{j=\varepsilon'}^{\varepsilon-1} z_{i,j}p^j$. Therefore, $z_i \bmod p^{\varepsilon'} = z_{i,0}$. This implies that for each polynomial $f_j$, the following is true:

$f_j(z_{i,0}) \equiv f_j(z_i) \bmod p^{\varepsilon'}$

$ $

Next, we derive the following:

$f_j(z_{i,0})\cdot p^j \equiv f_j(z_i)\cdot p^j \bmod p^{\varepsilon' + 1}$ (where $j \geq 1$)

$ $

The above is true because: 

$f_j(z_{i,0}) \equiv f_j(z_i) \bmod p^{\varepsilon'}$

$f_j(z_{i,0}) = f_j(z_i) + q\cdot p^{\varepsilon'}$ (for some integer $q$)

$f_j(z_{i,0})\cdot p^j = f_j(z_i)\cdot p^j + q\cdot p^{\varepsilon'}\cdot p^j$ \textcolor{red}{ $\rhd$ multiplying $p^j$ to both sides}

$f_j(z_{i,0})\cdot p^j = f_j(z_i)\cdot p^j + q\cdot p^{j-1} \cdot p^{\varepsilon'+1}$ \textcolor{red}{ $\rhd$ $f_j(z_{i,0})\cdot p^j$ and $f_j(z_i)\cdot p^j$ differ by some multiple of $p^{\varepsilon' + 1}$}

$ $

Therefore, $f_j(z_{i,0})\cdot p^j \equiv f_j(z_i)\cdot p^j \bmod p^{\varepsilon' + 1}$.

$ $

Now, given step 5's claim ($z_i^p \equiv z_{i,0} + \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i,0})\cdot p^j \bmod p^{\varepsilon'+1}$), we can derive the following:

$z_i^p - \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i})\cdot p^j \bmod p^{\varepsilon' + 1}$

$\equiv (z_{i,0} + \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i,0})\cdot p^j) - \sum\limits_{j=1}^{\varepsilon'}f_j(z_{i})\cdot p^j \bmod p^{\varepsilon' + 1}$ \textcolor{red}{ $\rhd$ applying step 5's claim}

$\equiv (z_{i,0} + \sum\limits_{j=1}^{\varepsilon'}f_j(z_i)\cdot p^j) - \sum\limits_{j=1}^{\varepsilon'}f_j(z_i)\cdot p^j \bmod p^{\varepsilon' + 1}$ \textcolor{red}{ $\rhd$ applying $f_j(z_{i,0})\cdot p^j \equiv f_j(z_i)\cdot p^j \bmod p^{\varepsilon' + 1}$}

$\equiv z_{i,0} \bmod p^{\varepsilon' + 1}$

\end{myproof}

\item Finally, we define the lifting polynomial $F_{\varepsilon'}(z_i)$ as follows:

$F_{\varepsilon'}(z_i) = z_i^p - \sum\limits_{j=1}^{\varepsilon'}f_j(z_i)\cdot p^j$

$\textcolor{white}{F_{\varepsilon'}(z_i) } \equiv z_{i,0} \bmod p^{\varepsilon' + 1}$


The above relation implies that $F_{\varepsilon'}(x) \bmod p^{\varepsilon'+1}$ is equivalent to the least significant base-$p$ digit of $x$ (according to step 6's claim). Therefore, if we plug in $z_i$ into $F_{\varepsilon'}(x)$ and regard $\varepsilon' = 1$, then the output is some number whose least significant base-$p$ digit is $z_{i,0} \bmod p^2$ and the 2nd least significant base-$p$ digit is $0 \bmod p^2$. As we recursively apply the output back to $F_{\varepsilon'}(x)$ and increment $\varepsilon'$ by 1, we iteratively zero out the 2nd least significant base-$p$ digit, the 3rd least significant base-$p$ digit, and so on. We repeat this process for $\varepsilon-1$ times to zero out the upper $\varepsilon-1$ base-$p$ digits, keeping only the least significant digit as it is (i.e., $z_{i,0}$). Therefore, $F_{\varepsilon'}(x)$ is a valid lifting polynomial that can be iteratively used to extract the least significant digit of $z_i \bmod p^\varepsilon$. 


\end{enumerate}

We use $F_{\varepsilon'}(x)$ as the internal helper function within the digit extraction function $G_{\varepsilon}(z_i)$ that calls $F_{\varepsilon'}(x)$ a total of $v-1$ times.


\subsubsection{Summary}
\label{subsubsec:bfv-bootstrapping-summary}

We summarize the BFV bootstrapping procedure (with the generalization of $t = p^r$) as follows. 

\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{subsubsec:bfv-bootstrapping-summary}} BFV Bootstrapping}}]

Suppose we have an RLWE ciphertext $(A, B)  = \textsf{RLWE}_{S, \sigma}\bm(\Delta M + E\bm) \bmod q$, where $\Delta = \left\lfloor\dfrac{q}{t}\right\rfloor$ and $t = p^r$ (i.e., the plaintext modulus is a power of some prime), $r \in \mathbb{Z}$, and $r \geq 1$. 

$ $

\begin{enumerate}
\item \textbf{\underline{Modulus Switch} (from \boldmath$q \rightarrow p^\varepsilon$):} Scale down the ciphertext from $(A, B)$ to $\left(\left\lceil \dfrac{p^\varepsilon}{q}\cdot A\right\rfloor, \left\lceil \dfrac{p^\varepsilon}{q}\cdot B\right\rfloor\right) = (A', B')$ \textcolor{red}{ $\rhd$ where $p^\varepsilon \ll q$} 

$ $

$A'S + B' = p^{\varepsilon-r}M + E' \bmod p^\varepsilon$ \textcolor{red}{ $\rhd$ where $E' \approx \dfrac{p^\varepsilon}{q}\cdot E  + \left(\left\lfloor\dfrac{q}{p^r}\right\rfloor\cdot\dfrac{p^\varepsilon}{q} - p^{\varepsilon-r}\right)\cdot M$, which is a modulus switch noise plus the rounding noise caused by treating $\Delta=\left\lfloor\dfrac{q}{p^r}\right\rfloor \approx \dfrac{q}{p^r}$.}

$ $

\item \textbf{\underline{Homomorphic Decryption}:} With the bootstrapping key $\textsf{RLWE}_{S, \sigma}(\Delta' S) \bmod q$, homomorphically decrypt $(A', B') \bmod p^\varepsilon$ as follows:

$A' \cdot \textsf{RLWE}_{S, \sigma}(\Delta' S)  + B' = \textsf{RLWE}_{S, \sigma}\bm(\Delta' \cdot (p^{\varepsilon-r} M + E' + Kp^\varepsilon)\bm) \bmod q$ \textcolor{red}{ $\rhd$ where $\Delta' = \left\lfloor\dfrac{q}{p^\varepsilon}\right\rfloor$}

$ $

Now, we denote the modulus-switched noisy plaintext polynomial as $Z = p^{\varepsilon-r} M + E' + Kp^\varepsilon$.

$ $

\item \textbf{\textsf{\underline{CoeffToSlot}}:} Move the (encrypted) polynomial $Z$'s coefficients $z_0, z_i, \cdots, z_{n-1}$ to the input vector slots. This is done by computing: 

$\textsf{RLWE}_{S, \sigma}(\Delta' Z) \cdot n^{-1}\cdot \hathat{W}\cdot I_R^n$

$= \textsf{RLWE}_{S, \sigma}(\Delta' Z^{\langle1\rangle})$

, where $n^{-1}\cdot \hathat{W}\cdot I_R^n$ is the batch encoding matrix (Summary~\ref*{subsubsec:bfv-rotation-summary} in \autoref{subsubsec:bfv-rotation-summary}). 

$ $

\item \textbf{\underline{Digit Extraction}:} We design a polynomial $G_{\varepsilon}(z_i)$ (a digit extraction polynomial) as follows:

$z_i = d_0 + \left(\sum\limits_{j=\varepsilon'}^{\varepsilon-r} d_* p^j\right)$ \textcolor{red}{ $\rhd$ where $d_0 \in \mathbb{Z}_{p}$, and $\varepsilon'$ is $z_i$'s first least significant base-$p$ digit index whose value is non-zero (after digit index 0) currently being processed by the $F_{\varepsilon'}(Z_i)$ function}

$F_{\varepsilon'}(z_i) \equiv d_0 \bmod p^{\varepsilon'+1}$ \textcolor{red}{ $\rhd$ a $(p-1)$-degree polynomial recursively used to finally extract the value $d_0 \bmod p^{\varepsilon}$}

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

$ $



We homomorphically evaluate the digit extraction polynomial $G_{\varepsilon}$ recursively total $\varepsilon-r$ times at each coefficient $z_i$ of $Z$ stored at input vector slots, which zeros out and right-shifts the least significant (base-$p$) $\varepsilon-r$ digits of $z_i$ as follows:

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

$= m_i + k_i'p$

$ $

, provided $E'$'s each coefficient is smaller than $\left\|\dfrac{p^{\varepsilon-r}}{2}\right\|$. At this point, each input vector slot contains the noise-removed coefficient $m_i + k_i^{\langle \varepsilon - r - 1\rangle}p$. 

\para{\underline{Scaling Factor Re-interpretation}:} At each $i$-th round of digit extraction, we do not explicitly multiply $|p^{-1}|_q$ to perform division by $p$, but instead conceptually borrow this term from the denominator of the plaintext scaling factor $\Delta'$, conceptually updating the scaling factor to $\left\lfloor\dfrac{q}{p^{\varepsilon-i}}\right\rfloor$. This implies that at $i$-th round of digit extraction, the plaintext operations used for ciphertext-to-plaintext homomorphic operations should encode their values by using the scaling factor $\left\lfloor\dfrac{q}{p^{\varepsilon-i}}\right\rfloor$. At the end of digit extraction, the plaintext scaling factor becomes $\Delta' = \Delta = \left\lfloor\dfrac{q}{p^r}\right\rfloor$. 


$ $

\item \textbf{\textsf{\underline{SlotToCoeff}}:} Homomorphically move each input vector slot's value $m_i + k_i^{\langle \varepsilon - r - 1\rangle}p^\varepsilon$ back to the (encrypted) polynomial coefficient positions. This is done by multiplying $\hathat{W}^*$ to the output ciphertext of the digit extraction step, where $\hathat{W}^*$ is the decoding matrix (Summary~\ref*{subsubsec:bfv-rotation-summary} in \autoref{subsubsec:bfv-rotation-summary}). The output of this computation is $\textsf{RLWE}_{S, \sigma}\bm(\Delta\cdot (M + K^{\langle \varepsilon - r - 1\rangle}p) + E^{\langle \text{b} \rangle}) \bm) = \textsf{RLWE}_{S, \sigma}\bm(\Delta\cdot (M + E^{\langle \text{final} \rangle}) \bm) \bmod q$, where $E^{\langle \text{b} \rangle}$ is the new noise generated during bootstrapping (step $3\sim 5$). 




\end{enumerate}



\end{tcolorbox}

\para{The purpose of Homomorphic Decryption:} Its purpose is to temporarily adjust the scaling factor of the ciphertext to preserve the correctness of bootstrapping. Before homomorphic decryption, the ciphertext encrypts $p^{\varepsilon-r} M$, a message with the scaling factor $p^{\varepsilon-r}$. After homomorphic decryption, the ciphertext encrypts $\Delta' p^{\varepsilon-r} M$, the message $p^{\varepsilon-r} M$ with the scaling factor $\Delta' = \left\lfloor\dfrac{q}{p^{\varepsilon}}\right\rfloor$. This specific adjustment is needed for the scaling factor re-interpretation during each round of digit extraction to conceptually divide by $p$ (i.e., multiply by $|p^{-1}|_q$) and eventually adjust the scaling factor back to $\left\lfloor\dfrac{q}{p^r}\right\rfloor$ as the original form for standard BFV ciphertexts.