# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 5 Multi-Identity Based Full Homomorphic Encryption Scheme
### Construction  
The basic parameter definition of the scheme: Let \(n\) as security parameter, \(L\) denote the maximum depth of homomorphic calculation allowed for the circuit, \(q=q(n,L)\) be a sufficiently large prime, \(D\) denote the maximum number of distinct identities supported by the scheme, \(m,m^{\prime},\overline{m},w,k,N=(m+1)k\) and FRD encoding function \(H\) are the same as the definitions in the above IBFHE encryption scheme. According to the notation in [16], the gadget matrix \(M\in\mathbb{Z}^{m^{\prime}\times N}\) is extended to \(\hat{M}\in\mathbb{Z}_{q}^{Dm^{\prime}\times DN}\). According to lemma 2, it is known that for any matrix \(A\in\mathbb{Z}_{q}^{Dm^{\prime}\times DN}\), there exists a function \(\hat{M}^{-1}(\cdot)\) such that \(\hat{M}^{-1}(A)\in\{0,1\}^{DN\times DN}\), satisfying \(\hat{M}\hat{M}^{-1}(A)=A\). * **mIBFHE.Setup**\((1^{n},1^{L},1^{D}):\) Input the security parameter \(n\), the maximum depth \(L\) that the circuit allows homomorphic operations, and the maximum number of different identities \(D\) supported by the scheme. Run the **IBFHE.Setup** algorithm and output the master public key \(MPK=(A,u)\) and the master secret key \(MSK=R\). * **mIBFHE.Extract**\(\Big{(}MPK,MSK,\left[id_{j}\right]_{j\in[D]}\Big{)}:\) Input the master public key \(MPK\), master secret key \(MSK\), and user's identity vector \(\left[id_{j}\right]_{j\in[D]}\in\mathbb{Z}_{q}^{n}\). Run the **IBFHE.Extract** algorithm to generate secret key \(s_{id_{1}},\ldots,s_{id_{D}}\) corresponding to identity \(id_{1},\ldots,id_{D}\) and the related public key \({A^{\prime}}_{id_{1}},\ldots,{A^{\prime}}_{id_{D}}\), and construct the joint secret key by horizontally appending all the secret-keys in sequence \(\hat{s}=\left[s_{id_{1}},\ldots,s_{id_{D}}\right]\in\mathbb{Z}_{q}^{Dm^{\prime}}\). Output the public key \({A^{\prime}}_{id_{1}},\ldots,{A^{\prime}}_{id_{N}}\) and the joint secret key vector \(\hat{s}\). * **mIBFHE.Enc**\(\Big{(}MPK,\left[id_{j}\right]_{j\in[D]^{\prime}}\Big{[}{A^{\prime}}_{id_{j}} \Big{]}_{j\in[D]^{\prime}},\mu,i\Big{)}:\) Input the master public key \(MPK\), the user's identity vector \(\left[id_{j}\right]_{j\in[D]}\) and its corresponding public key \(\left[{A^{\prime}}_{id_{j}}\right]_{j\in[D]^{\prime}}\), the encrypted plaintext message \(\mu\in\{0,1\}\) and the identity \(i\in[D]\) that needs to be extended. Run the algorithm to output the extended ciphertext \(\hat{\mathbf{C}}_{i}\) corresponding to identity \(id_{i}\). The specific operation steps are as follows:  
1. **Single identity encryption step:** Run \(\textbf{IBFHE}.\textbf{Enc}(\textit{MPK},id_{i},\mu)\) to generate identity \(id_{i}\) single identity IBFHE ciphertext \(\mathbf{C}=\mathbf{A}_{id}^{T}\mathbf{Y}+\mu\mathbf{M}+\mathbf{E}\). In this step, the party (here the \(i\)-th party) keeps its \(\mathbf{Y}\) for the next step;
2. **Multi-identity ciphertext expansion step:** Input a single-identity ciphertext \(\mathbf{C}\), the public keys of the other parties, and a randomness \(\mathbf{Y}\) selected from \(\textbf{IBFHE}.\textbf{Enc}\). Execute steps (a)-(d) as follows: 1. \(\left\{ \begin{aligned} \mathbf{V}_{i,j}^{(\mathbf{x},\mathbf{t})}\\ \mathbf{V}_{i,j}^{(\mathbf{x},\mathbf{t})}\end{aligned} \right\}_{\mathbf{x}\in[n], \mathbf{t}\in[N]}\) \(\leftarrow\) \(\left\{ \begin{aligned} \textbf{IBFHE}.\textbf{Enc}(\textit{MPK},id_{i},\mathbf{Y} [\mathbf{x},\mathbf{t}])\\ \mathbf{V}_{i,j}^{(\mathbf{x},\mathbf{t})}\end{aligned} \right\}_{\mathbf{x}\in[n], \mathbf{t}\in[N]}\) \(\leftarrow\) \(\left\{ \begin{aligned} \textbf{IBFHE}.\textbf{Enc}(\textit{MPK},id_{i},\mathbf{ \overline{\mathbf{Y}}}[\mathbf{x},\mathbf{t}])\\ \end{aligned} \right\}_{\mathbf{x}\in[n],\mathbf{t}\in[N]}\) \(\text{for }j\in[D]\backslash\{i\}\), where \(\mathbf{Y}\) was chosen in the single identity encryption step and \(\mathbf{\overline{\mathbf{Y}}}\) is randomly chosen from \(\{0,1\}^{n\times N}\). 2. Compute \(\mathbf{X}_{i}^{j}\leftarrow\textbf{Link-Mask}\bigg{(}\left\{