## 3 New Multi-Key Variant of BGV
### Improved Multi-Key BGV
Then, for party \(i\) at level \(l\), compute the ciphertext \(\mathbf{c}_{l,i}=\left(c_{l,i}^{0},c_{l,i}^{1}\right)\in R_{Q_{l}}^{2}\) as \(\mathbf{c}_{l,i}=\left(c_{l,i}^{0},c_{l,i}^{1}\right)=\left(\mu+\mathbf{b}_{l,i}[0]\cdot r+p\cdot e,\mathbf{a}_{l}[0]\cdot r+p\cdot e^{\prime}\right)\ (\text{mod}\ Q_{l})\). Here, \(\mathbf{b}_{l,i}[0]\in R_{Q_{l}}\) and \(\mathbf{a}_{l}[0]\in R_{Q_{l}}\) denote the first component of the vectors \(\mathbf{b}_{l,i}\) and \(\mathbf{a}_{l}\), respectively. * \(\mathbf{MK-BGV.CText}(\mathbf{c},n^{*})\): The ciphertext extension algorithm is performed by the evaluator, such as a cloud server or another computation entity. Suppose \(\mathbf{c}=\left(c_{0},c_{1},\ldots,c_{n}\right)\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}^{*}=\left(c_{0}^{*},c_{1}^{*},\ldots,c_{n^{*}}^{*}\right)\in R_{Q_ {l}}^{n^{*}+1}\] by setting \(c_{0}^{*}=c_{0}\) and \(c_{i}^{*}=c_{i}\) for \(1\leq i\leq n\), while \(c_{i}^{*}=0\) for all \(i\) satisfying \(n<i\leq n^{*}\). This construction guarantees that \[c_{0}^{*}+\sum_{l=1}^{n^{*}}c_{i}^{*}\cdot s_{l,i}=c_{0}+\sum_{l=1}^{n}c_{i} \cdot s_{l,i}\ (\text{mod}\ Q_{l}).\] Thus, the extended ciphertext \(\mathbf{c}^{*}\) encrypts the same underlying plaintext at the same level while now being associated with \(n^{*}\) parties. * \(\mathbf{MK-BGV.Dec}(\mathbf{c},\left\{s_{l,i}\right\}_{i=1}^{n})\): The decryption algorithm is jointly executed by all involved parties. Given an \(n\)-key ciphertext \(\mathbf{c}=\left(c_{0},c_{1},\ldots,c_{n}\right)\in R_{Q_{l}}^{n+1}\) at level \(l\) associated with \(n\) parties, along with the corresponding secret keys \(\left\{s_{l,i}\right\}_{i=1}^{n}\), the plaintext \(\mu\) is recovered by computing \[\mu=\left(c_{0}+\sum_{l=1}^{n}c_{i}\cdot s_{l,i}\right)\text{mod}\ Q_{l}\text{ mod}\ p.\]
* \(\mathbf{MK-BGV.ModulusSwitch}(\mathbf{c})\): The modulus switching algorithm is executed by the evaluator. Given a ciphertext \(\mathbf{c}=\left(c_{0},c_{1},\ldots,c_{n}\right)\in R_{Q_{l}}^{n+1}\) at level \(l\), compute \[c_{i}^{\prime}\equiv\left\lfloor\frac{1}{q_{l}}\cdot c_{i}\right\rfloor(\text{ mod}\ p)\]for \(i=0,\ldots,n\), where \(\lfloor\cdot\rfloor\) denotes the rounding operation, and output the ciphertext \(\mathbf{c}^{\prime}=\left(c_{0}^{\prime},c_{1}^{\prime},\ldots,c_{n}^{\prime} \right)\in R_{\mathbb{Q}_{l-1}}^{n+1}\) at level \(l-1\). In BGV-type schemes, reducing the inner modulus from \(Q_{l}\) to \(Q_{l-1}\) decreases the internal noise by roughly the factor \(Q_{l-1}/Q_{l}=1/q_{l}\). The modulus switching technique ensures that the resulting ciphertext \(\mathbf{c}^{\prime}\) can still be decrypted under the same secret key without affecting the correctness of the underlying plaintext, enabling continued homomorphic computations at the lower level. A detailed correctness proof for modulus switching can be found in [5]. * \(\mathbf{MK-BGV.Eval}\left(\mathcal{C},\left\{\mathbf{b}_{i}\right\}_{i=1}^{n},\left(\mathbf{c}_{1},\ldots,\mathbf{c}_{x}\right)\right)\): The homomorphic evaluation algorithm is executed by the evaluator. Let \(\mathcal{C}\) denote the circuit provided as input for homomorphic evaluation on ciphertexts \(\left(\mathbf{c}_{1},\ldots,\mathbf{c}_{x}\right)\). 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. The algorithm proceeds as follows: 1. If any ciphertexts are at higher levels than others, apply the necessary key switching or modulus switching procedures so that all ciphertexts \(\mathbf{c}_{j}\) are converted to a common level \(l\). 2.