## 4 Batched MK-BGV Scheme
### Improved Batched Multi-Key \(Bgv\)  
Building upon the \(\mathbf{MK-BGV}\) scheme introduced in Section 3 and the ciphertext packing technique presented in Section 4.1, we now explicitly construct our final batched multi-hop BGV-type MKFHE scheme, termed \(\mathbf{BMK-BGV}\). The typical application model of \(\mathbf{BMK-BGV}\) is shown in Figure 1.  
* \(\mathbf{BMK-BGV.Setup}\big{(}1^{\lambda},1^{L}\big{)}\): For a given \(N\), \(\lambda\), and \(L\), where \(N\) denotes the RLWE dimension, \(L\) is a bound on the circuit depth, and \(\lambda\) is the security parameter, define a sequence of ciphertext moduli \(\big{\{}Q_{l}\big{\}}_{l=0}^{L}\) recursively as \(Q_{l}=\prod_{i=0}^{l}q_{i}\) for \(l=0,1,\ldots,L\), where each \(q_{i}\) is an integer. Specifically, the largest modulus is \(Q_{L}=q_{0}\cdot q_{1}\cdots q_{L}\). Let the error distribution \(\chi=\chi(\lambda)\) be a \(B_{\chi}\)-bounded spherical discrete Gaussian distribution \(D_{\mathbb{Z}^{N},\sigma}\) over the ring \(R\), where the bound satisfies \(B_{\chi}\ll Q_{0}\). Let \(p\in\mathbb{Z}\) be the plaintext modulus, chosen such that \(p\) is coprime with every \(Q_{l}\). Let \(H:R_{Q_{l}}\to R^{t}\) be a homomorphic gadget decomposition function associated with the gadget vector \(\mathbf{g}\in R_{Q_{l}}^{t}\). The mappings \(PCRT_{p}\) and \(PCRT_{p}^{-1}\) are isomorphisms between \(\mathbb{F}_{p^{d}}^{\xi}\) and \(R_{p}\). For each level \(l\), uniformly sample a random vector \(\mathbf{a}_{l}\gets U\Big{(}R_{Q_{l}}^{t}\Big{)}\). Output the public parameters \(pp=\big{(}R,\,p,\big{\{}Q_{l},\mathbf{a}_{l}\big{\}}_{l=0}^{L},\chi\big{)}\). * \(\mathbf{BMK-BGV.KeyGen}(pp)\): For each level \(l\) (from \(L\) down to \(0\)) and for the \(i\)-th party, output \(L+1\) secret-public key pairs \(\big{\{}(s_{l},\mathbf{b}_{l})\big{\}}_{l=0}^{L}\leftarrow\mathbf{MK-BGV.KeyGen} (pp)\). * \(\mathbf{BMK-BGV.Enc}\Big{(}\Big{\{}\mu_{j}\big{\}}_{j=0}^{\xi-1},\mathbf{b}_{l,j},\mathbf{a}_{l}\Big{)}\): For a plaintext vector \(\mathbf{\mu}_{i}=\big{(}\mu_{i,0},\mu_{i,1},\ldots,\mu_{i,\xi-1}\big{)}\in \mathbb{F}_{p^{d}}^{\xi}\), compute the aggregate plaintext \(\mu\gets PCRT_{p}(\mathbf{\mu}_{i})\in R_{p}\). Then, for party \(i\) at level \(l\), compute the ciphertext \(\mathbf{c}_{l,i}=\Big{(}c_{l,i}^{0},c_{l,i}^{1}\Big{)}\in R_{Q_{l}}^{2}\) as \(\mathbf{c}_{l,i}=\mathbf{MK-BGV.Enc}(\mu,\mathbf{b}_{l,i},\mathbf{a}_{l})\). * \(\mathbf{BMK-BGV.CTExt}(\mathbf{c},n^{*})\): Suppose \(\mathbf{c}=(c_{0},c_{1},\ldots,c_{n})\in R_{Q_{l}}^{n+1}\) is a ciphertext at level \(l\) associated with \(n\) parties. To extend this ciphertext to support \(n^{*}\) parties (with \(n^{*}\geq n\)), construct and output an extended ciphertext \(\mathbf{c}^{*}=\mathbf{MK-BGV.CTExt}(\mathbf{c},n^{*})\in R_{Q_{l}}^{n^{*}+1}\). * \(\mathbf{BMK-BGV.Dec}\big{(}\mathbf{c},\big{\{}s_{l,j}\big{\}}_{i=1}^{n}\big{)}\): Given an \(n\)-key ciphertext \(\mathbf{c}=(c_{0},c_{1},\ldots,c_{n})\in R_{Q_{l}}^{n+1}\) at level \(l\) associated with \(n\) parties, along with the corresponding secret keys \(\big{\{}s_{l,j}\big{\}}_{i=1}^{n}\), the aggregate plaintext \(\mu\) is recovered by computing \(\mu=(c_{0}+\sum_{i=1}^{n}c_{i}\cdot s_{l,i})\text{mod}\ Q_{l}\text{mod}\ p\). Subsequently, the complete set of plaintext messages across the \(\xi\) slots is obtained via the inverse mapping \[\big{(}\mu_{0},\mu_{1},\ldots,\mu_{\xi-1}\big{)}\gets PCRT_{p}^{-1}(\mu) \in\mathbb{F}_{p^{d}}^{\xi}.\]
* \(\mathbf{BMK-BGV.Eval}\big{(}\mathcal{C},\big{\{}\mathbf{b}_{i}\big{\}}_{i=1}^{ n},(\mathbf{c}_{1},\ldots,\mathbf{c}_{x})\big{)}\): Let \(\mathcal{C}\) denote the circuit provided as input for homomorphic evaluation on ciphertexts (\(\mathbf{c}_{1},\ldots,\mathbf{c}_{x}\)). Each ciphertext \(\mathbf{c}_{j}\) (where \(j=1,\ldots,x\)) is at a particular level and was originally encrypted under a subset of the parties' keys.