# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 5 Multi-Identity Full Homomorphic Encryption Scheme
### Correctness and Parameters  
During the encryption phase, the ciphertext is extended to \(\hat{\mathbf{C}}_{id_{i}}\), and the noise term \(\widetilde{\beta}_{enc}=\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{id_{ i}}-\hat{\mathbf{e}}_{app}\) is calculated, where \(\big{\|}\mathbf{E}_{id_{i}}\big{\|}\leq B_{\chi}\). We compute:  
\[\Big{\|}\widetilde{\beta}_{enc}\Big{\|}=\Big{\|}\hat{\mathbf{s}}\hat{\mathbf{k} }_{id}\mathbf{E}_{id_{i}}-\hat{\mathbf{e}}_{app}\Big{\|}\leq\Big{\|}\hat{ \mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{id_{i}}\Big{\|}-\big{\|}\hat{ \mathbf{e}}_{app}\Big{\|}=DB_{\chi}\Big{(}m^{{}^{\prime}}\Big{)}-p,\]  
so the noise level of the ciphertext \(\hat{\mathbf{C}}_{id_{i}}\) is \(DB_{\chi}\Big{(}m^{{}^{\prime}}\Big{)}-p\). We refer to \(\hat{\mathbf{C}}_{id_{i}}\) as a ciphertext with noise level \(DB_{\chi}\Big{(}m^{{}^{\prime}}\Big{)}-p\).  
During the homomorphic computation phase, the noise generated by homomorphic multiplication is the largest, so we mainly analyze the noise of homomorphic multiplication. The computation process of homomorphic multiplication is as follows:\[\begin{split}\text{GSW.Multi}\big{(}\hat{\mathbf{C}}_{id_{1}},\hat{ \mathbf{C}}_{id_{2}}\big{)}&=\hat{\mathbf{C}}_{id_{1}}\cdot \mathbf{G}_{Dm^{\prime}}^{-1}\big{(}\hat{\mathbf{C}}_{id_{2}}\big{)}\\ &=\big{(}\mathbf{X}_{id_{1}}+msg_{1}\mathbf{G}_{Dm^{\prime}}+ \mathbf{E}_{id_{1}}\big{)}\cdot\mathbf{G}_{Dm^{\prime}}^{-1}\big{(}\hat{ \mathbf{C}}_{id_{2}}\big{)}\\ &=\big{(}\mathbf{X}_{id_{1}}+\mathbf{E}_{id_{1}}\big{)}\cdot \mathbf{G}_{Dm^{\prime}}^{-1}\big{(}\hat{\mathbf{C}}_{id_{2}}\big{)}\quad+msg_ {1}\big{(}\mathbf{X}_{id_{2}}+msg_{2}\mathbf{G}_{Dm^{\prime}}+\mathbf{E}_{id_{ 2}}\big{)}\\ &=msg_{1}msg_{2}\mathbf{G}_{Dm^{\prime}}\quad+\big{(}\mathbf{X}_ {id_{1}}+\mathbf{E}_{id_{1}}\big{)}\cdot\mathbf{G}_{Dm^{\prime}}^{-1}\big{(} \hat{\mathbf{C}}_{id_{2}}\big{)}\quad+msg_{1}\big{(}\mathbf{X}_{id_{2}}+ \mathbf{E}_{id_{2}}\big{)}.\end{split}\]  
Thus, we have:  
\[\begin{split}\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\hat{\mathbf{C }}_{id}^{\times}&=\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\hat{ \mathbf{C}}_{id_{1}}^{\times}\cdot\mathbf{G}_{Dm^{\prime}}^{-1}\big{(}\hat{ \mathbf{C}}_{id_{2}}\big{)}\\ &=msg_{1}msg_{2}\mathbf{s}\hat{\mathbf{k}}_{id}\mathbf{G}_{Dm^{ \prime}}\quad+\big{(}\hat{\mathbf{e}}_{app_{1}}+\hat{\mathbf{s}}\hat{\mathbf{ k}}_{id}\mathbf{E}_{id_{1}}\mathbf{G}_{Dm^{\prime}}^{-1}\big{)}\big{(}\hat{ \mathbf{C}}_{id_{2}}\big{)}\\ &\quad+msg_{1}\big{(}-\hat{\mathbf{e}}_{app_{2}}+\hat{\mathbf{ s}}\hat{\mathbf{k}}_{id}\hat{\mathbf{E}}_{id_{2}}\big{)}.\end{split}\]  
Then, the homomorphic computation error is  
\[\widetilde{\hat{\beta}}_{eval}=\Big{(}-\hat{\mathbf{e}}_{app_{1}}+\hat{ \mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{id_{1}}\mathbf{G}_{Km^{\prime}}^{ -1}\Big{)}\big{(}\hat{\mathbf{C}}_{id_{2}}\big{)}+msg_{1}\Big{(}-\hat{\mathbf{ e}}_{app_{2}}+\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{id_{2}}\Big{)}\]  
Based on the analysis of circuit noise growth, with error control under correct decryption conditions, we can infer the upper bounds on the circuit computation depth \(L\) and the number of users \(D\) involved in the computation.  
\[\left\|\widetilde{\hat{\beta}}_{eval}\right\|=\left\|\Big{(}-\hat{\mathbf{e}} _{app_{1}}+\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{id_{1}}\mathbf{G} _{Dm^{\prime}}^{-1}\Big{)}\big{(}\hat{\mathbf{C}}_{id_{2}}\big{)}+msg_{1}\Big{(} -\hat{\mathbf{e}}_{app_{2}}+\hat{\mathbf{s}}\hat{\mathbf{k}}_{id}\mathbf{E}_{ id_{2}}\big{)}\right\|\leq D^{2}\big{(}B_{\chi}\cdot\omega\cdot m^{\prime}-p\big{)}\]  
The final error is:  
\[\left\|\widetilde{\hat{\beta}}_{eval}\right\|\leq D^{2^{L}}\big{(}B_{\chi}\cdot \omega\cdot m^{\prime}-p\big{)} \tag{3}\]  
When the noise is less than \(\frac{Q}{\mathcal{A}}\), the decryption algorithm can correctly decrypt. Therefore, by selecting \(Q\geq D^{2^{L}}(B_{\chi}\cdot\omega\cdot m^{\prime}-p)\), the WZ-MIBFHE scheme can correctly decrypt.