## 3 Building Block
### Homomorphic Properties of Basic Encryption  
Homomorphic addition:  
Let \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\) be the ciphertexts encrypted under \(s\). According to Lemma 3, we get \(\left[\left\langle\mathbf{c_{i}},(1,s)\right\rangle\right]_{q}=\left\lfloor\frac{q }{2}\right\rfloor\cdot m_{i}+\widetilde{\mathbf{c}}_{i}\), \(i\in[2]\). It holds that:  
\[\left\langle\mathbf{c_{1}}+\mathbf{c_{2}},(1,s)\right\rangle=\left\lfloor\frac{q}{2} \right\rfloor\cdot\left[m_{1}+m_{2}\right]_{2}+\widetilde{\mathbf{c}}_{1}+ \widetilde{\mathbf{c}}_{2}-2\cdot\mathbf{\epsilon}\cdot w\]  
where \(\mathbf{\epsilon}=\frac{q}{2}-\left\lfloor\frac{q}{2}\right\rfloor<1\) and \(m_{1}+m_{2}=\left[m_{1}+m_{2}\right]_{2}+2\cdot w\), with \(\|w\|<1\). Let \(e_{add}:=\widetilde{\mathbf{c}}_{1}+\widetilde{\mathbf{c}}_{2}-2\cdot\mathbf{\epsilon}\cdot w\) and \(\|e_{add}\|<2\cdot(E+1)\). Here, \(E\) is the bound of the original noise term, i.e., \(\|\widetilde{\mathbf{c}}_{i}\|<E\), \(i\in[2]\). We get Lemma 4. **Lemma 4**. : _Let \(\mathbf{c_{add}}=\mathbf{c_{1}}+\mathbf{c_{2}}\) and \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\) be the ciphertexts encrypted under \(s\). Then:_  
\[\left[\left\langle\mathbf{c_{add}},(1,s)\right\rangle\right]_{q}=\left\lfloor\frac{ q}{2}\right\rfloor\cdot\left[m_{1}+m_{2}\right]_{2}+e_{add}\]  
_where \(\|e_{add}\|<2\cdot(E+1)\). The addition decryption is correct when \(\|e_{add}\|<\left\lfloor\frac{q}{2}\right\rfloor/2\)._  
Homomorphic multiplication:  
Let \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\) be the ciphertexts encrypted under \(s\) and \(\mathbf{c_{mult}}\) be a multiplicative ciphertext corresponding to \(\mathbf{c_{1}}\), \(\mathbf{c_{2}}\). To preserve the homomorphism of the multiplication, the following structure is needed:  
\[\left[\mathbf{c_{mult}},(1,s)\right]_{q}=\left\lfloor\frac{q}{2}\right\rfloor\cdot m _{1}\cdot m_{2}+e_{mult}.\]  
The tensor product is used to implement ciphertext multiplication to keep the structure divided by \(\frac{q}{2}\). Therefore, we define \(\mathbf{c_{mult}}=\left\lfloor\frac{2}{q}\cdot\mathbf{c_{1}}\otimes\mathbf{c_{2}}\right\rfloor\) and the secret key should be \(\mathbf{s}^{\prime}=(1,s)\otimes(1,s)\). We will discuss how to use our new key switching technology to replace the keys after homomorphic multiplication in Section 3.3. Here, we continue to discuss how the ciphertext multiplication obtains homomorphism. \[\langle c_{mult},s^{\prime}\rangle=\langle\left\lfloor\frac{2}{q}\cdot c_{1} \otimes c_{2}\right\rceil,s^{\prime}\rangle\text{ mod }q\]  
Set \(\widetilde{\mathbf{c}}=\left\lfloor\frac{2}{q}\cdot c_{1}\otimes c_{2}\right\rceil- \frac{2}{q}\cdot c_{1}\otimes c_{2}\) with \(\|\widetilde{\mathbf{c}}\|\leq 1/2\). Let \(\xi_{1}:=\langle\widetilde{\mathbf{c}},s^{\prime}\rangle\) and \(\|\xi_{1}\|<\|\widetilde{\mathbf{c}}\|\cdot\|s^{\prime}\|_{1}<\frac{1}{2}\cdot( \delta_{R}+1)^{2}\). Using the properties of tensor product, we get:  
\[\langle c_{mult},s^{\prime}\rangle-\xi_{1}=\frac{2}{q}\cdot\langle c_{1},(1,s )\rangle\cdot\langle c_{2},(1,s)\rangle. \tag{2}\]  
According to Equation (1), we get:  
\[ \begin{split}\langle c_{j},(1,s)\rangle=\left\lfloor\frac{q}{2} \right\rfloor&\cdot m_{j}+\widetilde{e_{j}}\text{ mod }q\\ =\left\lfloor\frac{q}{2}\right\rfloor&\cdot m_{j}+ \widetilde{e_{j}}+q\cdot p_{j}.\end{split}  \tag{3}\]  
It is easy to get \(\|q\cdot p_{j}\|<\delta_{R}\cdot\|\varepsilon_{j}\|\cdot\|(1,s)\|\) and \(\|v_{j}\|<\delta_{R}\), where \(j\in[2]\). Plugging Equation (3) into Equation (2), we get:  
\[ \begin{split}\langle c_{mult},s^{\prime}-\xi_{1}\rangle& =\frac{2}{q}\cdot\left(\left\lfloor\frac{q}{2}\right\rfloor& \cdot m_{1}+\widetilde{e}_{1}+q\cdot p_{1}\right)\cdot\left(\left\lfloor\frac{ q}{2}\right\rfloor&\cdot m_{2}+\widetilde{e}_{2}+q\cdot p_{2} \right)\\ &=\left\lfloor\frac{q}{2}\right\rfloor&\cdot m_{1} \cdot m_{2}+\xi_{2}+q\cdot(m_{1}v_{2}+m_{2}v_{1}+2v_{1}v_{2}).\end{split}