## 3 New Multi-Key Variant of BGV
### Improved Multi-Key BGV
Because negating \(s_{l,i}\) remains within the same error distribution \(\chi\) and multiplying by \(p\) merely rescales the noise, \((\mathbf{a}_{l},\mathbf{b}_{l,i})\) still constitutes an RLWE sample. Therefore, by the RLWE assumption, \(\mathbf{b}_{l,i}\) is computationally indistinguishable from a uniform random vector in \(R_{Q_{l}}^{t}\). A ciphertext at level \(l\) similarly has a form \(\mathbf{c}_{l,i}=\left(c_{l,i}^{0},c_{l,i}^{1}\right)\in R_{Q_{l}}^{2}\) where \(c_{l,i}^{0}=\mu+\mathbf{b}_{l,i}[0]r+pe\pmod{Q_{l}}\) and \(c_{l,i}^{1}=\mathbf{a}_{l}[0]r+pe^{\prime}\pmod{Q_{l}}\). Here, \(\left(\mathbf{b}_{l,i}[0],c_{l,i}^{0}\right)\) and \(\left(\mathbf{a}_{l}[0],c_{l,i}^{1}\right)\) each can be viewed as an RLWE sample with secret \(r\), in which \(c_{l,i}^{0}\) contains a plaintext \(\mu\) in an otherwise random encryption of zero. Hence, \(\mathbf{c}_{l,i}=\left(c_{l,i}^{0},c_{l,i}^{1}\right)\) is computationally indistinguishable from a random pair in \(\mathit{U}\!\left(R_{Q_{l}}^{2}\right)\) under the RLWE assumption. To formally prove the IND-CPA security of our \(\mathbf{MK-BGV}\) scheme under the RLWE assumption, we construct a hybrid argument consisting of two experiments: Hybrid 0 (the real IND-CPA experiment) and Hybrid 1 (an indistinguishable variant), and then argue their computational indistinguishability. The experiments are defined according to Definition 2 and aim to show that no PPT adversary can distinguish between the encryptions of any two chosen plaintexts with non-negligible advantage. Hybrid 0: Let \(n\in\mathbb{N}\) denote the number of participating parties. The experiment proceeds as follows:  
1. For each party \(i\in\{1,\ldots,n\}\), the challenger generates key pairs \(\left\{(s_{l,i},\mathbf{b}_{l,i})\right\}_{l=0}^{L}\leftarrow\mathbf{MK-BGV.KeyGen }(pp)\), and sends the public keys \(\left\{\mathbf{b}_{l,i}\right\}_{l=0}^{L}\) to the adversary \(\mathcal{A}\). 2. The adversary \(\mathcal{A}\) selects two plaintexts \(\mu_{0},\mu_{1}\in R_{p}\), and specifies a public key \(\mathbf{b}_{l,i}\) to be used for encryption. 3. The challenger samples a uniform bit \(b\in\{0,1\}\), and returns the ciphertext \(\mathbf{c}_{l,i}=\mathbf{MK-BGV.Enc}(\mu_{b},\mathbf{b}_{l,i},\mathbf{a}_{l})\) to \(\mathcal{A}\). 4. \(\mathcal{A}\) outputs a guess bit \(b^{\prime}\in\{0,1\}\). The experiment outputs \(1\) if \(b^{\prime}=b\), and \(0\) otherwise. Let this experiment be denoted by \(\mathrm{Exp}_{0}(\lambda)\). Hybrid 1: This experiment is identical to Hybrid 0, except that the challenger encrypts the other message, i.e., \(\mu_{1-b}\), instead of \(\mu_{b}\). The same public key \(\mathbf{b}_{l,i}\) specified by the adversary is used. 1. All key generation and public key disclosure steps remain unchanged. 2. The adversary submits the same two plaintexts \(\mu_{0},\mu_{1}\in R_{p}\) and public key \(\mathbf{b}_{l,i}\) as in Hybrid 0. 3. The challenger samples the same bit \(b\in\{0,1\}\), but now computes \(\mathbf{c}_{l,i}^{\prime}=\mathbf{MK-BGV.Enc}(\mu_{1-b},\mathbf{b}_{l,i}, \mathbf{a}_{l})\), and returns it to \(\mathcal{A}\). 4. \(\mathcal{A}\) outputs a guess bit \(b^{\prime}\in\{0,1\}\). The experiment outputs \(1\) if \(b^{\prime}=b\), and \(0\) otherwise. Let this experiment be denoted by \(\mathrm{Exp}_{1}(\lambda)\). In Hybrid 0, the challenge ciphertext is generated as \(\mathbf{c}_{l,i}=(\mu_{b}+\mathbf{b}_{l,i}[0]r+pe,\mathbf{a}_{l}[0]r+pe^{\prime}) \pmod{Q_{l}}\), while in Hybrid 1, the ciphertext is constructed as \(\mathbf{c}_{l,i}^{\prime}=(\mu_{1-b}+\mathbf{b}_{l,i}[0]r+pe,\)\(\mathbf{a}_{l}[0]r+pe^{\prime})\pmod{Q_{l}}\). As analyzed earlier, both ciphertexts \(\mathbf{c}_{l,i}\) and \(\mathbf{c}_{l,i}^{\prime}\) are computationally indistinguishable from uniformly random pairs in \(R_{Q_{l}}^{2}\) under the RLWE assumption. Since both ciphertexts are independently computationally indistinguishable from uniform, they are also computationally indistinguishable from each other.