## 3 New Multi-Key Variant of BGV
### Novel Methods for Evaluation Key Generation and Key Switching
Specifically, since \(\mathbf{a}_{l}\), \(\mathbf{a}_{l-1}\), and \(\mathbf{v}_{l,i}\) are random vectors, and \(\mathbf{b}_{l-1,i}\) is computationally indistinguishable from a random vector in \(U\left(R_{Q_{l-1}}^{t}\right)\) (making it pseudorandom), replacing \(\mathbf{u}_{l,i}\), \(\mathbf{v}_{l,i}\), \(\mathbf{w}_{l,i}\), and \(\mathbf{x}_{i,j}\) by random vectors \(\mathbf{u}^{\prime},\mathbf{v}^{\prime},\mathbf{w}^{\prime},\mathbf{x}^{ \prime}\gets U\left(R_{Q_{l}}^{t}\right)\) is computationally indistinguishable under the same RLWE assumption with parameters \((N,Q_{l},\chi)\) and the corresponding secrets \(m_{l,i}\), \(s_{l,i}\) or \(s_{l-1,i}^{-1}\). Consequently, the distribution of each evaluation key \(\mathcal{K}_{l,i}=(\mathbf{u}_{l,i},\mathbf{v}_{l,i},\mathbf{w}_{l,i},\mathbf{ x}_{i,j})\in R_{Q_{l}}^{t\times 4}\) is computationally indistinguishable from \(U\left(R_{Q_{l}}^{t\times 4}\right)\). **Correctness:** To demonstrate the correctness of the key switching procedure, it suffices to show that the standard ciphertext output in the last step decrypts to the original plaintext under the new secret keys. Formally, we need to ensure \(\mu=\sum_{i,j=0}^{n}c_{i,j}\cdot s_{l,i}s_{l,j}=c_{0}^{\ddagger}+\sum_{i=1}^{ n}c_{i}^{\ddagger}\cdot s_{l-1,i}\ (\text{mod}\ Q_{l})(\text{mod}\ p)\). We first examine the intermediate ciphertext \(\mathbf{c}^{\ddagger}=\left(c_{0}^{\ddagger},c_{1}^{\ddagger},\ldots,c_{n}^{ \ddagger}\right)\) generated in Step 3 of the algorithm. One can verify that  
\[\begin{array}{rl}c_{0}^{\ddagger}+\sum\limits_{i=1}^{n}c_{i}^{\ddagger} \cdot s_{l,i}&=c_{0,0}+\sum\limits_{j=1}^{n}z_{j}\boxplus\mathbf{w}_{l,j}+ \sum\limits_{i=1}^{n}\left(c_{i,0}+c_{0,i}\right)\cdot s_{l,i}+\sum\limits_{  
Hence, we obtain the desired equality \(c_{0}^{\prime}+\sum_{i=1}^{n}c_{i}^{\prime}\cdot s_{l-1,i}=\sum_{i,j=0}^{n}c_{i,j }\cdot s_{l,j}s_{l,j}\)\((\bmod Q_{l})(\bmod p)\) which is exactly the intended decryption condition. This confirms the correctness of the key switching algorithm. **Performance:** As an informal overview, our proposed evaluation key generation and key switching algorithms already provide superior parameter sizes and practical efficiency compared to the mainstream approaches in [16; 17; 19]. In [16; 17], for each level, each party must run an additional GSW-type MKFHE protocol to generate its own evaluation key generation materials, and the public keys and associated materials of all participating parties must be combined to produce a large shared evaluation key. In contrast, our \(\mathbf{MK-BGV}\) scheme achieves the same multi-party functionality without incurring these burdens. Moreover, in each key switching procedure, our evaluation key size is only \(4 tnN\lceil\log Q_{l}\rceil\), whereas [16; 17] require \(4 tn^{2}N\lceil\log Q_{l}\rceil\) and \(t(n+1)^{2}N\lceil\log Q_{l}\rceil\), respectively. Compared to [19], our **SwitchKey** algorithm leverages a precomputation of \(z_{i}\) in Step 3 so that, when updating \(\left(c_{0}^{\dagger},c_{i}^{\dagger}\right)\), only \(n^{2}+2n\) external products are required, instead of the \(4n^{2}\) external products needed in their procedure. A more detailed performance analysis and comparison is presented in Section 5.