# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 5 Multi-Identity Based Full Homomorphic Encryption Scheme  
### Link-Mask Scheme  
Based on the above IBFHE scheme, we constructed an efficient multi-identity fully homomorphic encryption scheme by using the extended ciphertext method and the masking scheme, which is denoted as mIBFHE. Firstly, we introduce the general method of converting single identity IBFHE scheme into multi identity scheme. For the convenience of description, we describe our scheme as a simple example. Assuming that there are two parties \((D=2)\), any polynomial number of parties \(D\) can be extended by this method. Let \(\mathbf{C}_{1}\) and \(\mathbf{C}_{2}\) be the ciphertexts of the plaintext messages \(\mu_{1}\) and \(\mu_{2}\) corresponding to the parties' identities \(id_{1}\) and \(id_{2}\) in the IBFHE scheme, respectively, and the identities \(id_{1}\) and \(id_{2}\) correspond to the secret keys \(\mathbf{s}_{1}\) and \(\mathbf{s}_{2}\), respectively, which satisfy \(\mathbf{s}_{1}^{\mathsf{T}}\mathbf{C}_{1}=\mu_{1}\mathbf{s}_{1}^{\mathsf{T}}\mathbf{M}+\mathbf{e}_ {1}\), \(\mathbf{s}_{2}^{\mathsf{T}}\mathbf{C}_{2}=\mu_{2}\mathbf{s}_{2}^{\mathsf{T}}\mathbf{M}+\mathbf{e}_ {2}\). By extending ciphertext \(\mathbf{C}_{1},\mathbf{C}_{2}\in\mathbb{Z}_{q}^{m^{\prime}\times N}\) according to the number of parties \(D\) to \"extended\" ciphertext \(\hat{\mathbf{C}}_{1},\hat{\mathbf{C}}_{2}\in\mathbb{Z}_{q}^{2m^{\prime}\times 2N}\), those satisfy  
\[ \begin{bmatrix}\mathbf{s}_{1}^{\mathsf{T}},\mathbf{s}_{2}^{\mathsf{T}}\end{bmatrix}  \hat{\mathbf{C}}_{1}=\mu_{1} \begin{bmatrix}\mathbf{s}_{1}^{\mathsf{T}},\mathbf{s}_{2}^{ \mathsf{T}}\end{bmatrix}\begin{bmatrix}\mathbf{M}&0\\ 0&\mathbf{M}\end{bmatrix} +\text{small error}\]  
\[ \begin{bmatrix}\mathbf{s}_{1}^{\mathsf{T}},\mathbf{s}_{2}^{\mathsf{T}}\end{bmatrix}  \hat{\mathbf{C}}_{2}=\mu_{2} \begin{bmatrix}\mathbf{s}_{1}^{\mathsf{T}},\mathbf{s}_{2}^{ \mathsf{T}}\end{bmatrix}\begin{bmatrix}\mathbf{M}&0\\ 0&\mathbf{M}\end{bmatrix} +\text{small error}\]  
In this paper, the general method of converting single-identity IBFHE scheme into multi-identity mIBFHE scheme is to convert the encrypted ciphertext matrix under single identity into a \(Dm^{\prime}\times DN\)-dimensional general extended matrix, and the scale of extended ciphertext is expanded by \(D^{2}\). In this way, ciphertexts \(\hat{\mathbf{C}}_{1}\) and \(\hat{\mathbf{C}}\) corresponding to different identities \(id\) can be input into the same Boolean circuit \(f\in\mathbb{C}\) for homomorphic operation. In order to perform the above ciphertext expansion, we need to construct a masking scheme: this scheme allows each party \((D_{1},D_{2})\) to independently generate key pairs, which are \((\mathbf{s}_{1},pk_{1})\), \((\mathbf{s}_{2},pk_{2})\) respectively. \(D_{1}\) Run the **IBFHE.Enc** algorithm to encrypt plaintext message \(\mu_{1}\) under \(pk_{1}\), and then use \(pk_{2}\) and its own randomness to extend its ciphertext. In the ciphertext expansion step, \(D_{1}\) runs the masking algorithm twice (the number of parties) to use \(pk_{1},pk_{2}\) to create matrices \(X_{1}^{j},\overline{X}_{1}^{2}\), where \(j\in[2]\), \(\mathbf{s}_{1}^{\mathsf{T}}X_{1}^{1}\approx 0\), \(\mathbf{s}_{2}^{\mathsf{T}}\big{(}\mathbf{C}_{1}-X_{1}^{2}\big{)}\approx\mu_{1}\mathbf{M}\), and \(\mathbf{s}_{2}^{\mathsf{T}}\overline{X}_{1}^{2}\approx 0\). Then, we randomly chose a matrix \(\mathbf{Q}\) and set a matrix \(\mathbf{Q}_{2}\) such that \(\mathbf{s}_{2}^{\mathsf{T}}\mathbf{Q}_{2}\approx\mathbf{s}_{1}^{\mathsf{T}}\mathbf{Q}\). Therefore, the final multi-identity extended ciphertext form of \(D_{1}\) is  
\[\hat{\mathbf{C}}_{1}= \begin{bmatrix}\mathbf{C}_{1}^{1}&\mathbf{Q}\\ 0&\mathbf{C}_{1}^{2}\end{bmatrix} \]  
where \(\mathbf{C}_{1}\) is a single identity IBFHE ciphertext of \(D_{1}\), \(\mathbf{C}_{1}^{1}=\mathbf{C}_{1}-X_{1}^{1}\) and \(\mathbf{C}_{1}^{2}=\mathbf{C}_{1}-X_{1}^{2}+\overline{X}_{1}^{2}-\mathbf{Q}_{2}\). There is\[