# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 5 Multi-Identity Based Full Homomorphic Encryption Scheme
### Link-Mask Scheme
\begin{split}&\big{[}s_{1}^{\mathsf{T}},s_{2}^{\mathsf{T}}\big{]} \hat{C}_{1}=\big{[}s_{1}^{\mathsf{T}},s_{2}^{\mathsf{T}}\big{]}\left[\begin{array} []{cc}C_{1}^{\mathsf{T}}&Q\\ 0&C_{1}^{\mathsf{T}}\end{array}\right]\\ &=\Big{[}s_{1}^{\mathsf{T}}C_{1}^{\mathsf{T}},s_{1}^{\mathsf{T}}Q+s_{2}^{ \mathsf{T}}C_{1}^{\mathsf{T}}\Big{]}\approx\mu_{1}\big{[}s_{1}^{\mathsf{T}},s _{2}^{\mathsf{T}}\big{]}\bigg{[}\begin{array}{cc}M&0\\ 0&M\end{array}\bigg{]}\end{split} \]  
Similarly, the ciphertext \(C_{2}\) is extended to \(\hat{C}_{2}\), which can perform homomorphic operations on ciphertext \(\hat{C}_{1}\) and \(\hat{C}_{2}\) encrypted under different identities. Before constructing a specific masking scheme, we need to reconstruct the ciphertext extension of CM15 on the basis of [30]. The operation is as follows. **Link-Mask. ** Let \(\mathbf{Y}\in\{0,1\}^{n\times N}\) be a 0-1 matrix, and \(\mathbf{V}^{(\mathbf{x},\mathbf{t})}\) be a IBFHE ciphertext of \(\mathbf{Y}[\mathbf{x},\mathbf{t}]\) (\(\mathbf{x}\)-th row and \(\mathbf{t}\)-th column of \(\mathbf{Y}\), \(\mathbf{x}\in[n],\mathbf{t}\in[N]\)) under \((pk,sk)=(\mathbf{A},\mathbf{s})\). Let \((pk^{\prime},sk^{\prime})=(\mathbf{A}^{\prime},\mathbf{s}^{\prime})\) be another IBFHE key pair. There exists a polynomial-time deterministic algorithm \(\textbf{Link-Mask}\big{(}pk^{\prime},\big{(}\mathbf{V}^{1,1},\ldots,\mathbf{V}^{n,N} \big{)}\big{)}\), input \(pk^{\prime}\) and encryptions \(\mathbf{V}^{(\mathbf{x},\mathbf{t})}\), return a matrix \(X\in\mathbb{Z}_{q}^{m^{\prime}\times N}\), satisfying \(\mathbf{s}^{\mathsf{T}}X=\mathbf{s}^{\mathsf{T}}\mathbf{A}^{\prime\mathsf{T}}\mathbf{ Y}+\mathbf{e}\), where \(\left\lVert\mathbf{e}\right\rVert_{\infty}\leq n(m+1)^{2}\beta\). The algorithm is as follows (Algorithm 1). ```
Input:\(pk^{\prime}\) and \(\big{\{}\mathbf{V}^{(\mathbf{x},\mathbf{t})}\big{\}}_{\mathbf{x}\in[n],\mathbf{t}\in[N]}\) Output:\(X\in\mathbb{Z}_{q}^{m^{\prime}\times N}\) (1) Define \(\mathbf{L}_{\mathbf{x},\mathbf{t}}\in\mathbb{Z}_{q}^{m^{\prime}\times N}\), for \(\mathbf{x}\in[n]\), \(\mathbf{t}\in[N]\) by \[\mathbf{L}_{\mathbf{x},\mathbf{t}}[\mathbf{a},\mathbf{b}]= \begin{cases}\mathbf{A}^{\prime\mathsf{T}}[ \mathbf{a},\mathbf{x}]&\mathbf{t}=\mathbf{b}\\ 0&\text{other}\end{cases} \] (2) Output:\(X=\sum_{\mathbf{x}=1}^{n}\sum\limits_{\mathbf{t}=1}^{N}\mathbf{V}^{(\mathbf{x},\mathbf{t})}\mathbf{M}^{-1} (\mathbf{L}_{\mathbf{x},\mathbf{t}})\in\mathbb{Z}_{q}^{m^{\prime}\times N}\). ```  
**Algorithm 1**Link-Mask. **Proof. ** Since \(\mathbf{V}^{(\mathbf{x},\mathbf{t})}\) is a IBFHE ciphertext of \(\mathbf{Y}[\mathbf{x},\mathbf{t}]\) under \((pk,sk)=(\mathbf{A},\mathbf{s})\), we have \(\mathbf{s}^{\mathsf{T}}\mathbf{V}^{(\mathbf{x},\mathbf{t})}=\mathbf{Y}[\mathbf{x},\mathbf{t}]\mathbf{s }^{\mathsf{T}}\mathbf{M}+\mathbf{e}_{\mathbf{x},\mathbf{t}}\). Hence, it holds that  
\[ \begin{split}\mathbf{s}^{\mathsf{T}}\mathbf{X}&=\mathbf{s}^ {\mathsf{T}}\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\mathbf{V}^{(\mathbf{x},\mathbf{t})}\mathbf{M}^{-1} (\mathbf{L}_{\mathbf{x},\mathbf{t}})\\ &=\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\Big{(}\mathbf{Y}[\mathbf{x},\mathbf{t}] \mathbf{s}^{\mathsf{T}}\mathbf{M}+\mathbf{e}_{\mathbf{x},\mathbf{t}}\Big{)}\mathbf{M}^{-1}(\mathbf{L}_{ \mathbf{x},\mathbf{t}})\\ &=\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\Big{(}\mathbf{Y}[\mathbf{x},\mathbf{t}] \mathbf{s}^{\mathsf{T}}\mathbf{L}_{\mathbf{x},\mathbf{t}}+\mathbf{e}_{\mathbf{x},\mathbf{t}}^{{}^{ \prime}}\mathbf{M}^{-1}(\mathbf{L}_{\mathbf{x},\mathbf{t}})\Big{)}\\ &=\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\Big{(}\mathbf{Y}[\mathbf{x},\mathbf{t}] \mathbf{s}^{\mathsf{T}}\mathbf{L}_{\mathbf{x},\mathbf{t}}+\mathbf{e}_{\mathbf{x},\mathbf{t}}^{{}^{ \prime}}\mathbf{t}\Big{)}.\\ &=\mathbf{s}^{\mathsf{T}}\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\mathbf{Y}[ \mathbf{x},\mathbf{t}]\mathbf{L}_{\mathbf{x},\mathbf{t}}+\sum\limits_{\mathbf{x},\mathbf{t}}^{n,N}\mathbf{e}_{ \mathbf{x},\mathbf{t}}^{{}^{\prime}}\end{split}