## 3 New Multi-Key Variant of BGV
### Redesigning Homomorphic Multiplication
The expression for \(c_{0}^{\intercal}+\sum_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,j}\) expands as:\[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\] \[=c_{0}c_{0}^{\prime}+\sum\limits_{i=1}^{n}\left(c_{i}\boxempty{ \bf z}\right)\boxempty{\bf(w}_{l,i}+{\bf v}_{l,i}\cdot s_{l,j}\right)+\sum \limits_{i=1}^{n}\left(c_{i}c_{0}^{\prime}+c_{0}c_{i}^{\prime}\right)\cdot s_ {l,j}+\sum\limits_{j=1}^{n}\left(c_{j}^{\prime}\boxempty{\bf y}\right)\cdot s_ {l,j}\left(\mbox{mod }Q_{l}\right)(\mbox{mod }p)\]  
Using the homomorphic properties of the gadget decomposition \(H(\cdot)\) and the relation  
\[{\bf u}_{l,i}\cdot s_{l,j}=-{\bf a}_{l}\cdot s_{l,j}\cdot m_{l,i}+s_{l,i} \cdot s_{l,j}\cdot{\bf g}+p\cdot s_{l,j}\cdot{\bf e}_{l,i}^{\prime}={\bf b}_{ l,j}\cdot m_{l,i}+s_{l,i}s_{l,j}{\bf g}\;(\mbox{mod }Q_{l})(\mbox{mod }p),\]  
the term \(\sum_{j=1}^{n}\left(c_{j}^{\prime}\boxempty{\bf y}\right)\cdot s_{l,j}\) becomes:  
\[\sum\limits_{j=1}^{n}\left(c_{j}^{\prime}\boxempty{\bf y}\right) \cdot s_{l,j} =\sum\limits_{j=1}^{n}c_{j}^{\prime}\boxempty{\left(\sum\limits_ {i=1}^{n}H(c_{i})\odot{\bf u}_{i,j}\right)\cdot s_{l,j}\] \[=\sum\limits_{i,j=1}^{n}\left\langle H(c_{j}^{\prime}),H(c_{i}) \odot{\bf u}_{i,j}\right\rangle\cdot s_{l,j}\] \[=\sum\limits_{i,j=1}^{n}\left\langle H(c_{i})\odot H\left(c_{j}^ {\prime}\right),{\bf u}_{i,j}\right\rangle\cdot s_{l,j}\] \[=\sum\limits_{i,j=1}^{n}\left\langle H(c_{i})\odot H\left(c_{j}^ {\prime}\right),{\bf b}_{l,j}\right\rangle\cdot m_{l,i}+\sum\limits_{i,j=1}^{n }c_{i}c_{j}^{\prime}\cdot s_{l,j}s_{l,j}\;(\mbox{mod }Q_{l})(\mbox{mod }p)\]  
Similarly, using the relation \({\bf w}_{l,i}+{\bf v}_{l,i}s_{l,i}=-m_{l,i}{\bf g}\;(\mbox{mod }Q_{l})(\mbox{mod }p)\), we obtain:  
\[\sum\limits_{i=1}^{n}\left(c_{i}\boxempty{\bf z}\right)\boxempty{ \bf(w}_{l,i}+{\bf v}_{l,i}\cdot s_{l,j}\right) =-\sum\limits_{i=1}^{n}\left(c_{i}\boxempty{\bf z}\right)\cdot m_ {l,j}\] \[=-\sum\limits_{i=1}^{n}\left(c_{i}\boxempty{\bf z}\right)\boxempty {\bf(w}_{l,i}+{\bf v}_{l,i}\cdot s_{l,j}\right)\] \[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\]0 \[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\]1  
Combining all terms together, we arrive at:  
\[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\]2 \[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\]3 \[c_{0}^{\intercal}+\sum\limits_{i=1}^{n}c_{i}^{\intercal}\cdot s_{l,i} =c_{0}\cdot c_{0}^{\prime}+\sum\limits_{i=1}^{n}c_{i}\boxempty{\bf z }\boxempty{\bf w}_{l,i}+\sum\limits_{i=1}^{n}\left(c_{i}\cdot c_{0}^{\prime}+c_ {0}\cdot c_{i}^{\prime}\right)\cdot s_{l,i}+\sum\limits_{j=1}^{n}\left(c_{j}^{ \prime}\boxempty{\bf y}\right)\cdot s_{l,j}+\sum\limits_{i=1}^{n}c_{i}\boxempty{ \bf z}\boxempty{\bf v}_{l,i}\cdot s_{l,i}\]4  
This shows that the intermediate ciphertext \({\bf c}^{\intercal}\) is correctly normalized and decryptable under the original secret keys.