## 3 New Multi-Key Variant of BGV
### Improved Multi-Key BGV  
Throughout this work, we adopt the standard convention used in leveled FHE schemes, where the evaluation of the input circuit proceeds from the highest level (the initial input level) down to level 0 (the final output level). Accordingly, the index variable \(l\), which denotes the level index, ranges from high to low, and operations involving \(l-1\)--such as evaluation key generation, key switching, modulus switching, and homomorphic evaluation--are only performed at levels \(l\geq 1\), and are not invoked at level 0. In this section, we focus on presenting the overall structure of our \(\textbf{MK}-\textbf{BGV}\) scheme and provide an outline of the full homomorphic evaluation procedure. The formal algorithms for evaluation key generation and key switching--**EvkGen** and **SwitchKey**--will be described in detail in Section 3.2. * \(\textbf{MK}-\textbf{BGV}.\textbf{Setup}\left(1^{\lambda},1^{L}\right)\): For a given \(N\), \(\lambda\), and \(L\), where \(N\) denotes the RLWE dimension, \(L\) is a bound on the circuit depth, and \(\lambda\) is the security parameter, define a sequence of ciphertext moduli \(\{Q_{l}\}_{l=0}^{L}\) recursively as \(Q_{l}=\prod_{l=0}^{\dagger}q_{i}\) for \(l=0,1,\ldots,L\), where each \(q_{i}\) is an integer. Specifically, the largest modulus is \(Q_{L}=q_{0}\cdot q_{1}\cdots q_{L}\). Let the error distribution \(\chi=\chi(\lambda)\) be a \(B_{\chi}\)-bounded spherical discrete Gaussian distribution \(D_{Z^{N},\sigma}\) over the ring \(R\), where the bound satisfies \(B_{\chi}\ll Q_{0}\). Let \(p\in\mathbb{Z}\) be the plaintext modulus, chosen such that \(p\) is coprime with every \(Q_{l}\). Let \(h:R_{Q_{l}}\to R^{l}\) be a gadget decomposition function associated with the gadget vector \(\textbf{g}\in R^{l}_{Q_{l}}\). For each level \(l\), uniformly sample a random vector \(\mathbf{a}_{l}\gets U\left(R_{Q_{l}}^{t}\right).\) Output the public parameters \(pp=\left(R,\ p,\left\{Q_{l},\mathbf{a}_{l}\right\}_{l=0}^{L},\chi\right)\). In practical deployments, the **Setup** algorithm is executed once in a trusted setup phase, during which the public parameters are generated. This setup may be performed by a trusted third party (e.g., a cloud service provider) or collaboratively via a distributed multi-party protocol. Once established, the public parameters remain fixed and publicly known. * \(\mathbf{MK-BGV.KeyGen}(pp)\): The key generation algorithm is executed independently by each party without requiring any interaction or coordination with others. For each level \(l\) (from \(L\) down to \(0\)) and for the \(i\)-th party, the secret key is sampled as \(s_{l,i}\gets\chi,\) ensuring that \(s_{l,i}\) is invertible in \(R_{Q_{l}}\). A noise vector is drawn as \(\mathbf{e}_{l,i}\leftarrow\chi^{t}\). The public key is then computed by \(\mathbf{b}_{l,i}=-\mathbf{a}_{l}s_{l,i}+p\mathbf{e}_{l,i}\ (\text{mod}\ Q_{l})\), where \(\mathbf{b}_{l,i}\in R_{Q_{l}}^{t}\). Thus, the key generation algorithm outputs \(L+1\) pairs \(\left\{(s_{l,i},\mathbf{b}_{l,i})\right\}_{l=0}^{L}\) for each party \(i\). As detailed in [23; 32], efficient algorithms exist to verify whether an element in \(R_{Q_{l}}\) is invertible and to compute its inverse. Moreover, when setting \(Q_{l}=\Omega(n)\), elements that belong to \(R_{Q_{l}}\) are invertible with overwhelming probability. We point out that since \(\chi\) is a distribution over \(R\), and \(R_{Q_{l}}\) is defined as \(R/(Q_{l}R)\), the sampled secret key \(s_{l,i}\) is naturally an element of \(R_{Q_{l}}\)[5; 33]. * \(\mathbf{MK-BGV.Enc}(\mu,\mathbf{b}_{l,i},\mathbf{a}_{l})\): The encryption algorithm is performed locally by each data owner. For a plaintext \(\mu\in R_{p}\), sample a random element \(r\leftarrow\chi\), and noise \(e,e^{\prime}\leftarrow\chi\).