# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 5 Multi-Identity Based Full Homomorphic Encryption Scheme
### Construction
We recall that for a valid output \(X\) from **Link-Mask**\(\big{(}pk^{{}^{\prime}}\!\!,\big{(}\mathbf{V}^{\!,1}\!,\ldots,\mathbf{V}^{\!,n\!,N} \big{)}\big{)}\) with respect to a 0-1 matrix \(Y\), we have \(\mathbf{s}^{\text{T}}X=\mathbf{s}^{\text{T}}\mathbf{A}^{\prime\text{T}}\mathbf{Y}+\mathbf{e}\) for \(\mathbf{e}_{\infty}\leq n\left(m+1\right)^{2}\beta\). By the definition, we have  
\[\hat{\mathbf{s}}^{\text{T}}\hat{\mathbf{C}}_{i}=\Big{[}\mathbf{s}_{id_{1}}^{ \text{T}}\mathbf{C}_{i}^{1}+\mathbf{s}_{id_{1}}^{\text{T}}\!\!,\mathbf{Q}\!\ldots,\mathbf{s}_{ id_{i}}^{\text{T}}\mathbf{C}_{i}^{1},\ldots,\mathbf{s}_{id_{D}}^{\text{T}}\mathbf{C}_{i}^{ \text{D}}+\mathbf{s}_{id_{i}}^{\text{T}}\mathbf{Q}\Big{]}\] \[=\Big{[}\mathbf{s}_{id_{1}}^{\text{T}}\!\!\left(\mathbf{C}-X_{i}^{1}+\mathbf{ \overline{X}}_{i}^{1}-\mathbf{Q}_{1}\right)+\mathbf{s}_{id_{1}}^{\text{T}}\!\!,\mathbf{Q} \!\ldots,\mathbf{s}_{id_{i}}^{\text{T}}\big{(}\mathbf{C}-X_{i}^{i}\big{)}\,\] \[\ldots,\mathbf{s}_{id_{D}}^{\text{T}}\!\!\left(\mathbf{C}-X_{i}^{D}+\mathbf{ \overline{X}}_{i}^{D}-\mathbf{Q}_{D}\right)+\mathbf{s}_{id_{i}}^{\text{T}}\!\!,\mathbf{Q} \Big{]}\]  
Let's see how the bit message \(\mu\) is correctly recovered and check the error bound by using the following properties  
\[ \begin{array}{ll}\text{(1)}&\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{C}=\mathbf{s}_{id_{j }}^{\text{T}}\Big{(}\mathbf{A}_{id_{j}}^{\text{T}}\mathbf{Y}_{i}+\mu\mathbf{M}+\mathbf{E}\Big{)} =\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{A}_{id_{j}}^{\text{T}}\mathbf{Y}_{i}+\mu\mathbf{s}_{id_ {j}}^{\text{T}}\mathbf{M}+\mathbf{e}^{\prime},\text{ where }\parallel\mathbf{e}^{\prime}\parallel_{\infty}\leq\left(m+1 \right)\beta\ ;\\ \text{(2)}&\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{X}_{i}^{j}=\mathbf{s}_{id_{j}}^{\text{T}} \mathbf{A}_{id_{j}}^{\text{T}}\mathbf{Y}_{i}+\mathbf{e}_{j}^{\prime},\text{ where }\parallel\mathbf{e}_{j}^{\prime}\parallel_{\infty}\leq n\left(m+1\right)^{4}\beta;\\ \text{(3)}&\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{X}_{i}^{i}=\mathbf{s}_{id_{j}}^{\text{T}} \mathbf{A}_{id_{j}}^{\text{T}}\mathbf{Y}_{i}+\mathbf{e}_{j}^{\prime}=\widetilde{\mathbf{e}}_{ i},\text{ where }\parallel\mathbf{\tilde{e}}_{i}\parallel_{\infty}\leq n\Big{[}\left(m+1\right)^{4}+m+1 \Big{]}\beta;\\ \text{(4)}&\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{\overline{X}}_{i}^{\text{T}}=\mathbf{s}_{ id_{j}}^{\text{T}}\mathbf{A}_{id_{j}}^{\text{T}}\mathbf{\overline{Y}}+\mathbf{\tilde{e}}_{j}^{ \prime}=\widetilde{\mathbf{e}}_{j},\text{ where }\parallel\mathbf{\tilde{e}}_{j}\parallel_{\infty}\leq n\Big{[}\left(m+1 \right)^{4}+m+1\Big{]}\beta;\\ \text{(5)}&\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{Q}_{j}=\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{Q }+\mathbf{\tilde{e}}_{j},\text{ where }\parallel\mathbf{\tilde{e}}_{j}\parallel_{\infty}\leq\left(m+1\right)\beta;\\ \end{array} \]  
\[ \begin{array}{ll}\therefore\mathbf{s}_{id_{j}}^{\text{T}}\Big{(}\mathbf{C}-X_{i}^{j}+ \mathbf{\overline{X}}_{i}^{j}-\mathbf{Q}_{j}\Big{)}+\mathbf{s}_{id_{i}}^{\text{T}}\mathbf{Q} =\mu\mathbf{s}_{id_{j}}^{\text{T}}\mathbf{M}+\mathbf{\hat{e}}_{j}\\ \mathbf{s}_{id_{i}}^{\text{T}}\big{(}\mathbf{C}-X_{i}^{i}\big{)}=\mu\mathbf{s}_{id_{i}}^{ \text{T}}\mathbf{M}+\mathbf{\hat{e}}_{i}.\end{array} \]  
Therefore, we have \(\hat{\mathbf{s}}^{\text{T}}\hat{\mathbf{C}}_{i}=\mu\hat{\mathbf{s}}^{\text{T}}\hat{\mathbf{M}} +\mathbf{\hat{e}}\) where \(\mathbf{\hat{e}}=\big{[}\mathbf{\hat{e}}_{1},\ldots,\mathbf{\hat{e}}_{i},\ldots,\mathbf{\hat{e}}_ {D}\big{]}\in\mathbb{Z}_{q}^{D\times N}\) and \(\|\mathbf{\hat{e}}\|_{\infty}\leq\left[2n(m+1)^{4}+(n+1)(m+1)\beta\right]\). In the decryption procedure, this error is multiplied by \(\sqrt{DN}\). By our choice of the parameter, \(\sqrt{DN}\left[2n(m+1)^{4}+(n+1)(m+1)\beta\right]<\frac{q}{4}\). **Homomorphic property. ** The homomorphic property of the mIBFHE scheme follows directly from the IBFHE scheme in the fourth chapter, because the **m**IBFHE. **Eval algorithm is basically the same as the **IBFHE.