# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 5 Multi-Identity Based Full Homomorphic Encryption Scheme
### Construction
\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]^{\prime}}\mathbf{A}_{id_{i}}^{\prime}\bigg{)},j\in[D]\). 3. Choose \(\mathbf{Q}\stackrel{{\mathbf{S}}}{{\leftarrow}}\mathbb{Z}_{q}^{m^{ \prime}\times N}\). Set the matrix \(\mathbf{Q}_{h}\in\mathbb{Z}_{q}^{m^{\prime}\times N}\) having the last row \(\mathbf{s}_{id_{i}}\mathbf{Q}+\mathbf{\overline{\mathbf{e}}}_{h}\) and the rest rows zero, where \(\mathbf{s}_{id_{i}}\) is the secret key of the party \(i\), \(\mathbf{\overline{\mathbf{e}}}_{h}\) is chosen from \(\chi^{N}\), \(\forall h\in[D]\backslash\{i\}\). 4. Define the extended ciphertext matrix \(\hat{\mathbf{C}}_{i}\in\mathbb{Z}_{q}^{Dm^{\prime}\times DN}\) of the initial ciphertext \(\mathbf{C}\) as \[\hat{\mathbf{C}}_{i} \begin{bmatrix}\mathbf{C}_{i}^{1}&0&\cdots&0&0\\ 0&\mathbf{C}_{i}^{2}&\cdots&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ \mathbf{Q}&\cdots&\mathbf{C}_{i}^{\mathbf{t}}&\cdots&\mathbf{Q}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&\cdots&0&\mathbf{C}_{i}^{\mathbf{D}}\end{bmatrix} \] Which is concatenated by \(D^{2}\) number of \(m^{\prime}\times N\) sub-matrices. The diagonal sub-matrices of \(\hat{\mathbf{C}}_{i}\) are \(\mathbf{C}_{i}^{j}=\mathbf{C}-\mathbf{X}_{i}^{j}+\mathbf{\overline{\mathbf{X}}}_{i}^{j}-\mathbf{Q}_{j}\) for \(j\in[D]\backslash\{i\}\) and the \(i\)-th diagonal sub-matrix is \(\mathbf{C}-\mathbf{X}_{i}^{i}\). Lastly, \(\mathbf{Q}\) is on the \(i\)-th row and zero matrix \(0^{m^{\prime}\times N}\) is elsewhere. - \(\textbf{mlBFHE}.\textbf{Eval}(\textit{MPK},(\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C }}_{t}),f):\) Input the master public key \(\textit{MPK}\), Boolean circuit \(f\), and the extended ciphertext \(\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}\) which are the ciphertext encrypted under different identities \(id\). Output the operation ciphertext \(\hat{\mathbf{C}}=f(\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t})\), where the homomorphic addition is \(\hat{\mathbf{C}}_{Aid}=\hat{\mathbf{C}}_{1}+\hat{\mathbf{C}}_{2}\) and the homomorphic multiplication is \(\hat{\mathbf{C}}_{Mult}=\hat{\mathbf{C}}_{1}\mathbf{M}^{-1}(\hat{\mathbf{C}}_{2})\). According to the definitions of addition and multiplication, the homomorphic NAND operation is defined as \(\hat{\mathbf{C}}_{NAND}=\hat{\mathbf{M}}-\hat{\mathbf{C}}_{1}\hat{\mathbf{M}}^{-1}(\hat{\mathbf{C }}_{2})\). - \(\textbf{mlBFHE}.\textbf{Dec}(\textit{MPK},\hat{\mathbf{s}},\hat{\mathbf{C}})\): Input the master public key \(\textit{MPK}\), the joint secret key \(\hat{\mathbf{s}}\) and the extended ciphertext \(\hat{\mathbf{C}}\) to be decrypted. Set a vector \(\hat{\omega}=\left[\left\lfloor\frac{q}{2}\right\rfloor,0,\ldots,0\right]\in \mathbb{Z}_{q}^{Dm^{\prime}}\), compute \(\mu^{\prime}=\hat{\mathbf{s}}^{\intercal}.\hat{\mathbf{C}}\cdot\hat{\mathbf{M}}^{-1}(\hat{ \omega})\), and output \(\mu=\left\lfloor\frac{2\mu^{\prime}}{q}\right\rfloor\). **Correctness. ** Let \(\hat{\mathbf{C}}_{i}\) be the multi-identity ciphertext of a bit \(\mu\) by \(i\)-th user from the **m**IBFHE. **Enc algorithm:  
\[\hat{\mathbf{C}}_{i}\leftarrow\text{mIBFHE.Enc}\bigg{(}MPK_{\text{,}}\big{[}id_{i} \big{]}_{j\in[D]^{\prime}}\left[\mathbf{A}^{\prime}_{id_{i}}\right]_{j\in[D]^{ \prime}}\!\!,\mu,i\bigg{)}\]  
where \(\mathbf{C}\) is a single identity IBFHE ciphertext. For the joint secret key \(\hat{\mathbf{s}}=\big{[}\mathbf{s}_{id_{1}},\ldots,\mathbf{s}_{id_{D}}\big{]}\in\mathbb{Z} _{q}^{D^{\prime}}\) and the gadget matrix \(\hat{\mathbf{M}}\in\mathbb{Z}_{q}^{D^{\prime}\times DN}\), if \(\hat{\mathbf{C}}_{i}\) satisfies the relation \(\hat{\mathbf{s}}^{\text{T}}\hat{\mathbf{C}}_{i}\approx\mu\hat{\mathbf{s}}^{\text{T}}\hat{ \mathbf{M}}\), then we can naturally generalize the arguments of the scheme in [7]. The correctness of encryption and evaluation can be realized, and an effective mIBFHE scheme can be obtained. Now, we are ready to prove the correctness of multi-identity ciphertext.