## 4 Batch Leveled FHE Scheme
### Construction  
In this part, we will derive an RLWE-based leveled homomorphic encryption scheme named Batch.RFHE for batch processing. * Batch.RFHE.Setup\(\big{(}1^{L},1^{\lambda}\big{)}\) : Assume that the security parameter is \(\lambda\) and the circuit level is \(L\). Let \(R=\mathbb{Z}[x]/\Phi_{m}(x)\), where \(\Phi_{m}(x)=\prod\limits_{i=1}^{n}f_{i}(x)\) is a cyclotomic polynomial with degree \(\varphi(m)=d\), and the degree of each \(f_{i}(x)\) is \(d^{\prime}\), where \(\varphi(m)=d=n\cdot d^{\prime}\). Let \(q\) be the modulus. Let \(\chi=\chi(\lambda)\) be the error distribution over \(R\). \(\mathbb{F}_{2^{n^{\prime}}}^{n}\) the plaintext vector space, and the mapping CRT is the isomorphism mapping from \(\mathbb{F}_{2^{n^{\prime}}}^{n}\) to \(R_{2}\). * Batch.RFHE.KeyGen\(\big{(}1^{L},1^{\lambda}\big{)}\) : Sample \(L+1\) polynomials \(\{s_{0},\cdots,s_{L}\}\leftarrow\mathrm{RE.SecretKey}\) Gen\(\big{(}1^{\lambda}\big{)}\). Compute the public key: \(\mathbf{P}_{0}\leftarrow\mathrm{RE.PublicKeyGen}(\mathbf{s_{0}})\). For all \(i\in[L]\), define \(\mathbf{s}_{i-1}^{\prime}=(1,s_{i-1})\otimes(1,s_{i-1})\in R_{2}^{\lambda}\). Then, compute: \[\mathbf{W}_{(i-1)\to i}\leftarrow\mathrm{SwitchKeyGen}\big{(}\mathbf{s}_{i-1}^{ \prime},s_{i}\big{)}.\] Output \(pk=\mathbf{P}_{0}\), \(\mathit{evk}=\Big{\{}\mathbf{W}_{(i-1)\to i}\Big{\}}_{i\in[L]}\) and \(\mathit{sk}=\{s_{0},\cdots,s_{L}\}\). * Batch.RFHE.Enc\(\Big{(}pk,(n_{0},\cdots,m_{n-1})\in\mathbb{F}_{2^{d^{\prime}}}^{n}\Big{)}\): First, we use the polynomial-CRT to pack the plaintext \(m\gets CRT(m_{0},\cdots,m_{n-1})\in R_{2}\), then output \(c\leftarrow\mathrm{RE.Encrypt}(pk,m)\). * Batch.RFHE.Add\((\mathbf{c_{1}},\mathbf{c_{2}})\): Suppose the ciphertexts \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\) are respectively encrypted under \(s_{i-1}\) and \(s_{j-1}\). (1) If \(i\
eq j\), suppose \(i<j\), then repeat the following steps until \(i=j\) and turn to step (2): (a) \(\mathbf{c^{\prime}}=\mathbf{c_{1}}\otimes(1,0)\); (b) \(\mathbf{c_{1}}\leftarrow\mathrm{SwitchKey}\Big{(}\mathbf{W}_{(i-1)\to i},\mathbf{c^{ \prime}}\Big{)}\) ; (c) \(i=i+1\). (2) If \(i=j\), perform the following steps: (a) \(\mathbf{c^{\prime}}_{\mathbf{add}}=(\mathbf{c_{1}}+\mathbf{c_{2}})\otimes(1,0)\); (b) \(\mathbf{c_{add}}\leftarrow\mathrm{SwitchKey}\Big{(}\mathbf{W}_{(i-1)\to i^{\prime}}, \mathbf{c^{\prime}}_{\mathbf{add}}\Big{)}\) Batch.RFHE.Mult\((\mathbf{c_{1}},\mathbf{c_{2}})\): Suppose ciphertexts \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\) encrypted and \(s_{j-1}\). (1) If \(i\
eq j\), suppose \(i<j\), repeat the following steps until \(i=j\) and then turn to step (2):  
(a) \(\boldsymbol{c}^{\prime}=\boldsymbol{c}_{1}\otimes(1,0)\);  
(b) \(\boldsymbol{c}_{1}\leftarrow\mathrm{SwitchKey}\Big{(}\boldsymbol{W}_{(i-1) \to i},\boldsymbol{c}^{\prime}\Big{)}\) ;  
(c) \(i=i+1\). (2) If \(i=j\), perform the following steps:  
(a) \(\boldsymbol{c}^{\prime}_{\boldsymbol{mult}}=\lfloor\frac{2}{q}\cdot \boldsymbol{c}_{1}\otimes\boldsymbol{c}_{2}\rfloor\);  
(b) \(\boldsymbol{c}_{\boldsymbol{mult}}\leftarrow\mathrm{SwitchKey}\Big{(} \boldsymbol{W}_{(i-1)\to i},\boldsymbol{c}^{\prime}_{\boldsymbol{mult}} \Big{)}\). Batch.RFHE.Dec\((sk,\boldsymbol{c})\) : Assume that \(\boldsymbol{c}\) is encrypted under \(\mathrm{s}_{i}\). First compute:  
\[m\leftarrow\mathrm{RE.Decrypt}(\mathrm{s}_{i},\boldsymbol{c}).\]  
Then output:  
\[(m_{0},\cdots,m_{n-1})\gets CRT^{-1}(m)\in\mathbb{F}_{2}^{n}.\]  
The correctness of the scheme will be discussed together with the homomorphism of the scheme in Section 4.2. Lemma 8 (Security): _Let, \(q\), \(\chi\) be certain parameters, so that \(\mathrm{DRLWE}_{d,d,\chi}\) holds and \(L=L(d)\) is polynomially bounded.