## 3 New Multi-Key Variant of BGV
### Novel Methods for Evaluation Key Generation and Key Switching  
In this section, we present our scheme's approach for generating evaluation keys \((\mathbf{EvkGen})\) and performing key switching \((\mathbf{SwitchKey})\). * \(\mathbf{MK-BGV.EvkGen}(\mathbf{a}_{l},\mathbf{a}_{l-1},\mathbf{b}_{l-1,l^{ \prime}},s_{l,i}s_{l-1,j})\): For a party \(i\) at level \(l\), sample a random element \(m_{l,i}\leftarrow\chi\), a random vector \(\mathbf{v}_{l,i}\gets U\!\left(R_{Q_{l}}^{t}\right),\) and noise vectors \(\mathbf{e}_{l,i}^{\prime},\mathbf{e}_{l,i}^{\prime\prime},\mathbf{e}_{l,i}^{ \prime\prime}\leftarrow\chi^{l}\). Compute \(\mathbf{u}_{l,j}=-\mathbf{a}_{l}\cdot m_{l,j}+s_{l,j}\cdot\mathbf{g}+p\cdot \mathbf{e}_{l,j}^{\prime}(\mathrm{mod}Q_{l})\), \(\mathbf{w}_{l,j}=-\mathbf{v}_{l,j}\cdot s_{l,i}-m_{l,j}\cdot\mathbf{g}+p\cdot \mathbf{e}_{l,i}^{\prime\prime}(\mathrm{mod}Q_{l})\), and \(\mathbf{x}_{l,i}=\mathbf{b}_{l-1,i}\cdot s_{1-1,i}^{-1}+\mathbf{a}_{l-1}+s_{ l,i}\cdot s_{1-1,i}^{-1}\cdot\mathbf{g}+p\cdot\mathbf{e}_{l,i}^{\prime\prime}( \mathrm{mod}Q_{l})\). Then, output the evaluation key \(\mathcal{K}_{l,i}=(\mathbf{u}_{l,i},\mathbf{v}_{l,i},\mathbf{w}_{l,i},\mathbf{ x}_{l,i})\in R_{Q_{l}}^{l\times 4}\). We can observe that the evaluation key generation algorithm's input depends solely on the public parameters and the parties' own keys. Therefore, each party can generate its evaluation keys independently, and these evaluation keys in our scheme can be precomputed prior to encryption or homomorphic evaluation, and may even be stored publicly for potential future evaluations, irrespective of any changes in the set of participating parties. * \(\mathbf{MK-BGV.SwitchKey}\left(\mathbf{c}_{mult},\left\{(\mathbf{b}_{l,i}, \mathcal{K}_{l,i})\right\}_{i=1}^{n}\right)\): The key switching algorithm is executed by the evaluator. Consider a tensored ciphertext \(\mathbf{c}_{mult}=\left(c_{ij}\right)_{0\leq i,j\leq n}\) with each \(c_{ij}\in R_{Q_{l}}\), which is associated with the secret keys \(\left\{s_{l,i}\cdot s_{l,j}\right\}_{i,i=1}^{n}\), and a set of public keys \(\mathbf{b}_{l,i}\) together with evaluation keys \(\mathcal{K}_{l,i}=(\mathbf{u}_{l,i},\mathbf{v}_{l,i},\mathbf{w}_{l,i},\mathbf{ x}_{l,i})\) for \(i=1,\ldots,n\). To produce a standard ciphertext \(\mathbf{c}^{\prime}=\left(c_{0}^{\prime},c_{1}^{\prime},\ldots,c_{n}^{\prime} \right)\in R_{Q_{l}}^{n+1}\) at level \(l\) that is associated with the secret keys \(\left\{s_{l-1,i}\right\}_{i=1}^{n},\) perform the following steps:1. Set the first component as \(c_{0}^{\ddagger}=c_{0,0}\), and for each \(i=1,\ldots,n\), assign \(c_{i}^{\ddagger}=c_{i,0}+c_{0,i}(\text{mod}Q_{l})\). 2. For each \(j=1,\ldots,n\), update \(c_{j}^{\ddagger}=c_{j}^{\ddagger}+\sum_{i=1}^{n}\left(c_{i,j}\boxplus\mathbf{u} _{i,j}\right)(\text{mod}Q_{l})\). 3. For each \(i=1,\ldots,n\), compute \(z_{i}=\sum_{j=1}^{n}\left(c_{i,j}\boxplus\mathbf{b}_{i,j}\right)(\text{mod}Q _{l})\), and subsequently update \(\left(c_{0}^{\ddagger},c_{i}^{\ddagger}\right)=\left(c_{0}^{\ddagger},c_{i}^{ \ddagger}\right)+\left(z_{i}\boxplus\mathbf{w}_{i,j},z_{i}\boxplus\mathbf{v}_{ i,j}\right)(\text{mod}Q_{l})\). 4. For the intermediate ciphertext \(\mathbf{c}^{\ddagger}=\left(c_{0}^{\ddagger},c_{1}^{\ddagger},\ldots,c_{n}^{ \ddagger}\right)\in R_{Q_{l}}^{n+1}\), set \(c_{0}^{\prime}=c_{0}^{\ddagger}\) and for each \(i=1,\ldots,n\), compute \(c_{i}^{\ddagger}=c_{i}^{\ddagger}\boxplus\mathbf{x}_{i,j}(\text{mod}Q_{l})\). 5. Output the resulting ciphertext \(\mathbf{c}^{\prime}=\left(c_{0}^{\prime},c_{1}^{\dagger},\ldots,c_{n}^{ \prime}\right)\in R_{Q_{l}}^{n+1}\). **Security:** The security proofs for our evaluation key generation and key switching algorithms are essentially identical to the ciphertext security proofs presented in Section 3.1.