## 3 New Multi-Key Variant of BGV
### Redesigning Homomorphic Multiplication  
Although our key switching algorithm exhibits improved performance, we recognize that our MK-BGV scheme still offers substantial potential for further optimization. In particular, homomorphic multiplication remains the most expensive component, both in our construction and in existing batched MKFHE frameworks. We observe that the most complex parts of this operation are the tensor product and the ensuing key switching process, which require, respectively, \(O\big{(}n^{2}\big{)}\) ring multiplications and \(O\big{(}n^{2}\big{)}\) gadget decompositions. Consequently, these steps introduce a square-level complexity tied to the number of participating parties, significantly affecting the overall efficiency. In [20], a novel concept called homomorphic gadget decomposition is introduced. In essence, a homomorphic gadget decomposition function \(H(\cdot)\) not only satisfies the basic properties described in Section 2.5 but also allows arithmetic operations to be performed directly on the decomposed polynomials. Definition 3: **(Homomorphic Gadget Decomposition [20]). ** A function \(H:R_{Q}\to R^{t}\) is called a homomorphic gadget decomposition if, for any \(a,b\in R_{Q}\), it satisfies the following properties:  
\[\langle H(a)+H(b),\mathbf{g}\rangle=a+b\left(\bmod Q\right),\langle H(a) \odot H(b),\mathbf{g}\rangle=a\cdot b\left(\bmod Q\right)\]  
where \(\odot\) denotes the component-wise product, and \(\mathbf{g}\) is the fixed gadget vector. Inspired by this technique, we observe that \(H(a)+H(b)\) and \(H(a)\odot H(b)\) can serve as effectively bounded substitutes for \(H(a+b)\) and \(H(ab)\), since \(\left\|H(a)+H(b)\right\|_{\infty}\leq 2B_{H}\) and \(\left\|H(a)\odot H(b)\right\|_{\infty}\leq N\cdot B_{H}^{2}\). Leveraging this property, we redesign the homomorphic multiplication algorithm in our \(\mathbf{MK-BGV}\) scheme by merging the tensor product and key switching steps into a single process, thereby reducing the overall complexity from \(O\big{(}n^{2}\big{)}\) to \(O(n)\) ring multiplications and gadget decompositions. As a result, our new homomorphic multiplication algorithm achieves a linear complexity in terms of the number of participating parties. * \(\mathbf{MK-BGV.NewMult(c,c^{\prime},\big{\{}(b_{l,j},\mathcal{K}_{l,j})\}_{l=1 }^{n})}\): Consider two ciphertexts \(\mathbf{c}=(c_{0},c_{1},\dots,c_{n})\) and \(\mathbf{c^{\prime}}=\big{(}c_{0}^{\prime},c_{1}^{\prime},\dots,c_{n}^{\prime} \big{)}\) in \(R_{Q_{l}}^{n+1}\), together with a set of public keys \(\mathbf{b}_{l,i}\) and evaluation keys \(\mathcal{K}_{l,i}=(\mathbf{u}_{l,i}\boldsymbol{v}_{l,i}\boldsymbol{w}_{l,i} \boldsymbol{x}_{l,i})\) for \(i=1,\dots,n\). To produce the multiplied ciphertext \(\mathbf{c}^{\prime\prime}=\big{(}c_{0}^{\prime\prime},c_{1}^{\prime\prime}, \dots,c_{n}^{\prime\prime}\big{)}\in R_{Q_{l}}^{n+1}\) at level \(l\) that is associated with the secret keys \(\big{\{}s_{l-1,i}\big{\}}_{i=1}^{n}\), proceed as follows:Set the first component as \(c_{0}^{\intercal}=c_{0}\cdot c_{0}^{\prime}(\text{mod}Q_{l})\), and for each \(i=1,\ldots,n\), assign \(c_{i}^{\intercal}=c_{i}\cdot c_{0}^{\prime}+c_{0}\cdot c_{i}^{\prime}(\text{ mod}Q_{l})\). 2. Compute \(\mathbf{y}=\sum_{i=1}^{n}(H(c_{i})\odot\mathbf{u}_{i,j})(\text{mod}Q_{l})\) and \(\mathbf{z}=\sum_{j=1}^{n}\left(H\left(c_{j}^{\prime}\right)\odot\mathbf{b}_{ l,j}\right)(\text{mod}Q_{l})\). 3. For each \(j=1,\ldots,n\), update \(c_{j}^{\intercal}=c_{j}^{\intercal}+c_{j}^{\prime}\Box\mathbf{y}(\text{mod}Q _{l})\). 4. For each \(i=1,\ldots,n\), update \(\left(c_{0}^{\intercal},c_{1}^{\intercal}\right)=\left(c_{0}^{\intercal},c_{ 1}^{\intercal}\right)+\left(c_{i}\odot\mathbf{z}\odot\mathbf{w}_{i,j},c_{i} \odot\mathbf{z}\odot\mathbf{v}_{i,i}\right)\pmod{Q_{l}}\). 5.