## 3 Preliminaries
### Bootstrapping of CKKS  
The _ReScale_ operation is crucial for the homomorphic multiplication of ciphertexts. However, each _ReScale_ operation reduces the modulus of the ciphertext, which means there is a limit on the number of homomorphic multiplications that can be performed. Nevertheless, bootstrapping technology can solve this problem. The bootstrapping of CKKS mainly consists of four parts: _ModRaise_, _CoeffToSlot_, _EvalMod_, and _SlotToCoeff_.  
* _ModRaise_: If a ciphertext \(ct\) contains the plaintext \(m(X)=\left[\langle\mathrm{ct},\mathrm{sk}\rangle\right]_{q}\), then \(t(X)=\langle\mathrm{ct},\mathrm{sk}\rangle=qI(X)+m(X)\equiv m(X)(\bmod q)\), where \(\left|I(X)\right|_{\infty}<K=\mathcal{O}\Big{(}\sqrt{h}\,\Big{)}\), and \(\mathrm{h}\) is the number of \(1\) in \(\mathrm{sk}\). The purpose of _ModRaise_ is to increase the ciphertext modulus \(\mathrm{q}\) to a large modulus \(\mathrm{Q}\), such that \(\left[t(X)\right]_{Q}=t(X)\).
* _CoeffToSlot_: There is a modular reduction to be performed on the coefficients of the polynomial, but we need to approximate the modular reduction function using homomorphic addition and multiplication. Homomorphic addition and multiplication are done for the numbers in the slots, so we put the coefficients in the slots. This process is equivalent to a homomorphic ciphertext decoding operation, that is, for the matrix \(U_{0}\) and \(U_{1}\), homomorphic calculation \(z_{k}^{\prime}=\frac{1}{N}\Bigg{(}\overset{T}{U_{k}}\cdot z^{\prime}+U_{k}^{ T}\cdot\overset{-}{z^{\prime}}\Bigg{)}\), to obtain two ciphertexts encrypting vectors \(z_{0}^{\prime}=\Big{(}t_{0},\ldots,t_{\frac{N}{2}-1}\Big{)}\) and \(z_{1}^{\prime}=\Big{(}t_{\frac{N}{2}},\ldots,t_{N-1}\Big{)}\). \[U_{0}=\begin{bmatrix}1&\zeta_{0}&\ldots&\zeta_{0}^{\frac{N}{2}-1}\\ 1&\zeta_{1}&\ldots&\zeta_{1}^{\frac{N}{2}-1}\\ \vdots&\vdots&\ddots&\vdots\\ 1&\zeta_{\frac{N}{2}-1}&\ldots&\zeta_{\frac{N}{2}-1}^{\frac{N}{2}-1}\end{bmatrix} \text{ and }U_{1}=\begin{bmatrix}\zeta_{0}^{\frac{N}{2}}&\zeta_{0}^{\frac{N}{2}+1}& \ldots&\zeta_{0}^{N-1}\\ \zeta_{1}^{\frac{N}{2}}&\zeta_{1}^{\frac{N}{2}+1}&\ldots&\zeta_{1}^{N-1}\\ \vdots&\vdots&\ddots&\vdots\\ \zeta_{\frac{N}{2}-1}^{\frac{N}{2}}&\zeta_{\frac{N}{2}-1}^{\frac{N}{2}+1}& \ldots&\zeta_{\frac{N}{2}-1}^{N-1}\end{bmatrix}\] (1)
* _EvalMod_: The goal of _EvalMod_ is to homomorphically compute the modular reduction. Since the \(\left[\cdot\right]_{q}\) function is not a polynomial function, considering its periodicity, it can be approximated by a sine function to obtain \(S(t)=\frac{q}{2\pi}\mathrm{sin}\Big{(}\frac{2\pi t}{q}\Big{)}\). The Taylor polynomial is then used to approximate \(S(t)\) and the final approximation polynomial \(\frac{q}{2\pi}\sum\limits_{j=0}^{d-1}\frac{(-1)^{j}}{(2j+1)!}\Big{(}\frac{2\pi t }{q}\Big{)}^{2j+1}\) is obtained. In addition, the double angle formula \(\mathrm{cos}(2\theta)=\mathrm{cos}^{2}\theta-\mathrm{sin}^{2}\theta\) and \(\mathrm{sin}(2\theta)=2\mathrm{cos}\theta\cdot\mathrm{sin}\theta\) can be used to reduce the calculation cost [25].
* _SlotToCoeff_: _SlotToCoeff_ is the inverse process of _CoeffToSlot_, which restores the numbers in the slots to the coefficients of the polynomial. That is, for the given two encoded vectors \(z_{0}=\Big{(}m_{0},\cdots,m_{\frac{N}{2}-1}\Big{)}\) and \(z_{1}=\Big{(}m_{\frac{N}{2}},\cdots,m_{N-1}\Big{)}\), the linear transformation \(z=U_{0}\cdot z_{0}+U_{1}\cdot z_{1}\) is computed.