## 3 New Multi-Key Variant of BGV
### Improved Multi-Key BGV
For each ciphertext \(\mathbf{c}_{j}\), invoke the ciphertext extension algorithm \(\mathbf{MK-BGV.CText}\left(\mathbf{c}_{j},n\right)\) to extend \(\mathbf{c}_{j}\) into an extended ciphertext \(\mathbf{c}_{j}^{*}\) that is related to the union of all parties involved across these ciphertexts. This step ensures that all input ciphertexts are associated with the same set of \(n\) parties. 3. For each involved party \(i\), compute its level-\(l\) evaluation key \(\mathcal{K}_{l,i}=\mathbf{MK-BGV.EvkGen}\left(\mathbf{a}_{l},\mathbf{a}_{l-1}, \mathbf{b}_{l-1,i},\mathbf{c}_{l,j},\mathbf{c}_{l-1,i}\right)\). 4. To evaluate the circuit \(\mathcal{C}\) gate by gate, simply apply the homomorphic operations \(\mathbf{Add}\) and \(\mathbf{Mult}\) (detailed immediately below) on the extended ciphertexts. 5. After processing all gates in \(\mathcal{C}\), output the final ciphertext \(\mathbf{c}_{\text{out}}\), which encrypts the result of \(\mathcal{C}\) on the original plaintexts under the secret keys of all involved parties. * \(\mathbf{MK-BGV.Add}\left(\mathbf{c},\mathbf{c}^{\prime}\right)\): For two ciphertexts \(\mathbf{c}\) and \(\mathbf{c}^{\prime}\) in \(R_{\mathbb{Q}_{l}}^{n+1}\), output their component-wise sum \(\mathbf{c}^{\prime\prime}=\mathbf{c}+\mathbf{c}^{\prime}(\text{mod}Q_{l})\in R _{\mathbb{Q}_{l}}^{n+1}\). * \(\mathbf{MK-BGV.Multi}\left(\mathbf{c},\mathbf{c}^{\prime},\left\{\left(\mathbf{ b}_{l},\mathcal{K}_{l,i}\right)\right\}_{i=1}^{n}\right)\): Given ciphertexts \(\mathbf{c}=\left(c_{0},c_{1},\ldots,c_{n}\right)\) and \(\mathbf{c}^{\prime}=\left(c_{0}^{\prime},c_{1}^{\prime},\ldots,c_{n}^{\prime}\right)\) in \(R_{\mathbb{Q}}^{n+1}\) along with the public keys \(\left\{\mathbf{b}_{l,i}\right\}_{i=1}^{n}\) and evaluation keys \(\left\{\mathcal{K}_{l,i}\right\}_{i=1}^{n}\), compute the tensor product \(\mathbf{c}_{mult}=\mathbf{c}\otimes\mathbf{c}^{\prime}=\left(c_{i,j}\right) _{0\leq i,j\leq n}\in R_{\mathbb{Q}_{l}}^{\left(n+1\right)^{2}}\) with components \(c_{i,j}=c_{i}\cdot c_{j}^{\prime}\left(\text{mod}Q_{l}\right)\) for all \(0\leq i,j\leq n\). Then, compute \(\mathbf{c}^{\prime\prime}=\mathbf{MK-BGV.SwitchKey}\left(\mathbf{c}_{mult}, \left\{\left(\mathbf{b}_{l,i},\mathcal{K}_{l,i}\right)\right\}_{i=1}^{n}\right)\), and finally output \(\mathbf{c}^{\prime\prime}=\mathbf{MK-BGV.ModulusSwitch}\left(\mathbf{c}^{ \prime\prime}\right)\). **Security:** The security and correctness of our \(\mathbf{MK-BGV}\) scheme derive from the inherent properties of both the RLWE assumption (with parameters \(\left(N,Q_{l},\chi\right)\)) and the basic BGV scheme. As in most mainstream FHE schemes [5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20], we consider a static, passive adversarial model, in which an adversary may corrupt an arbitrary subset (possibly large but not all) of parties before the setup phase but cannot adaptively corrupt parties during the computation. The adversary can observe all public parameters, public keys, and ciphertexts throughout the execution, but cannot access the secret keys of honest parties. Furthermore, all parties are assumed to honestly follow the specified steps of the \(\mathbf{MK-BGV}\) scheme. In our scheme, elements and vectors are independently and randomly sampled from discrete Gaussian or uniform distributions, such as \(\chi\), \(\chi^{t}\), and \(U\left(R_{\mathbb{Q}_{l}}^{t}\right)\). This includes, for example, the secret keys \(\mathbf{s}_{l,i}\), noise vectors \(\mathbf{e}_{l,i}\), and random vectors \(\mathbf{a}_{l}\in R_{\mathbb{Q}_{l}}^{t}\). These distributions ensure sufficient entropy and unpredictability in parameter generation, thereby satisfying the security requirements under the RLWE assumption. For each level \(l\), a public key for party \(i\) is \(\mathbf{b}_{l,i}=-\mathbf{a}_{l}s_{l,i}+pe_{l,i}\pmod{Q_{l}}\in R_{Q_{l}}^{t}\), where \(\mathbf{a}_{l}\leftarrow\mathit{U}\!\left(R_{Q_{l}}^{t}\right),\ s_{l,i} \leftarrow\chi\), and \(\mathbf{e}_{l,i}\leftarrow\chi^{t}\).