## 3 New Multi-Key Variant of BGV
### Redesigning Homomorphic Multiplication
For the intermediate ciphertext \(\mathbf{c}^{\intercal}=\left(c_{0}^{\intercal},c_{1}^{\intercal},\ldots,c_{ n}^{\intercal}\right)\in R_{Q_{l}}^{n+1}\), set \(c_{0}^{{}^{\prime\prime}}=c_{0}^{\intercal}\) and for each \(i=1,\ldots,n\), compute \(c_{i}^{{}^{\prime\prime}}=c_{i}^{\intercal}\boxdot\mathbf{x}_{i,j}(\text{mod }Q_{l})\). Finally, output the resulting ciphertext \(\mathbf{c}^{\prime\prime}=\mathbf{MK}-\mathbf{BGV}.\mathbf{ModulusSwitch}( \mathbf{c}^{\prime\prime})\). **Performance:** In previous versions of the homomorphic multiplication algorithm, each component of a tensored ciphertext was computed as \(c_{i,j}=c_{i}\cdot c_{j}^{\prime}(\text{mod }Q_{l})\), which led to \(\mathcal{O}\left(n^{2}\right)\) computational complexity. By applying the homomorphic gadget decomposition, we substitute \(H\left(c_{i,j}\right)\) with the component-wise product of decompositions \(H(c_{i})\odot H\left(c_{j}^{\prime}\right)\). Equally significant, the component-wise product operation \(\odot\) is commutative and can be reordered without affecting the correctness of the inner product, thereby enabling further simplifications. Specifically, we can rewrite the expressions in Steps 2 and 3 of the **SwitchKey** algorithm as:  
\[ \begin{array}{ll}\sum\limits_{i=1}^{n}c_{i,j}\boxdot\mathbf{u}_{i,j}&= \sum\limits_{i=1}^{n}\left\langle H(c_{i})\odot H\left(c_{j}^{\prime}\right),\mathbf{u}_{i,j}\right\rangle\\ &=\left\langle H\left(c_{j}^{\prime}\right),\sum\limits_{i=1}^{n}H(c_{i}) \odot\mathbf{u}_{i,j}\right\rangle\\ &=c_{j}^{\prime}\boxdot\left(\sum\limits_{i=1}^{n}H(c_{i})\odot\mathbf{u}_{i, j}\right)\end{array} \]  
and similarly,  
\[ \begin{array}{ll}\sum\limits_{j=1}^{n}c_{i,j}\boxdot\mathbf{b}_{l,j}&= \sum\limits_{j=1}^{n}\left\langle H(c_{i})\odot H\left(c_{j}^{\prime}\right),\mathbf{b}_{l,j}\right\rangle\\ &=\left\langle H(c_{i}),\sum\limits_{j=1}^{n}H\left(c_{j}^{\prime}\right) \odot\mathbf{b}_{l,j}\right\rangle\\ &=c_{i}\boxdot\left(\sum\limits_{j=1}^{n}H\left(c_{j}^{\prime}\right)\odot \mathbf{b}_{l,j}\right)\end{array} \]  
Note that \(\sum_{i=1}^{n}H(c_{i})\odot\mathbf{u}_{i,i}\) is independent of index \(j\), and similarly, \(\sum_{j=1}^{n}H\left(c_{j}^{\prime}\right)\odot\mathbf{b}_{l,j}\) is independent of index \(i\). Thus, once computed, these values can be reused repeatedly for each subsequent external product computation, significantly reducing computational overhead. As a result, this optimization substantially decreases the number of required ring multiplications and gadget decompositions, both of which are scaled down to \(O(n)\). **Correctness:** To demonstrate the correctness of our new homomorphic multiplication algorithm, it suffices to show that the multiplied ciphertext \(\mathbf{c}^{\prime\prime}=\left(c_{0}^{\prime\prime},c_{1}^{\prime\prime}, \ldots,c_{n}^{\prime\prime}\right)\in R_{Q_{l}}^{n+1}\) from the multiplication of two \(n\)-key ciphertexts \(\mathbf{c}=\left(c_{0},c_{1},\ldots,c_{n}\right)\) and \(\mathbf{c}^{\prime}=\left(c_{0}^{\prime\prime},c_{1}^{\prime},\ldots,c_{n}^{ \prime}\right)\) decrypts correctly under the new secret keys \(\left\{s_{l-1,j}\right\}_{i=1}^{n}\). Formally, we need to verify that:  
\[\mu\cdot\mu^{\prime}=c_{0}^{\prime\prime}+\sum_{i=1}^{n}c_{i}^{\prime\prime} \cdot s_{l-1,i}=\left(c_{0}+\sum_{i=1}^{n}c_{i}\cdot s_{i,j}\right)\left(c_{0} ^{\prime}+\sum_{i=1}^{n}c_{i}^{\prime}\cdot s_{l,j}\right)\pmod{Q_{l}}(\text{ mod }p).\]  
We begin by analyzing the intermediate ciphertext \(\mathbf{c}^{\intercal}=\left(c_{0}^{\intercal},c_{1}^{\intercal},\ldots,c_{n}^{ \intercal}\right)\in R_{Q_{l}}^{n+1}\) generated in Step 4 of the algorithm.