# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 3 Identity-Based Encryption Scheme
### Security Reduction  
**Theorem 2. **_When \(m\geq 2n\log q\), if the \(\left(\mathbb{Z}_{q},n,\overline{\Psi}_{\alpha}\right)-LWE\) hardness assumption holds, the basic IBE scheme given in this section is IND-sID-CPA (Indistinguishable from Random, Select-Identity, Chosen-Plaintext Attachment) security._  
Proof. : For the IBE scheme proposed in this paper, we use a series of IND-sID-CPA security games proposed by [PERSON] et al. [26] under the standard model to prove the security. The security model is established by a sequence game between adversary \(\mathcal{A}\) and challenger \(\mathcal{C}\).The steps are as follows:  
**Game0** Game0 is a standard original IND-sID-CPA game between adversary \(\mathcal{A}\) and challenger \(\mathcal{C}\). **Game1** Let \(id^{*}\) be the identity of adversary \(\mathcal{A}\) who plans to attack. Compared with Game0, the challenger changes the way to generate matrix \(\mathbf{A}\), and randomly generates \(\mathbf{A}=\left[\overline{\mathbf{A}}\right]-\mathbf{H}_{id^{*}}\mathbf{G}-\overline{\mathbf{A}} \mathbf{R}\). From lemma 3, we can see that **GenTrap** algorithm in Game0 generates matrix \(\mathbf{A}=\left[\overline{\mathbf{A}}|\mathbf{H}_{id}\mathbf{G}-\overline{\mathbf{A}}\mathbf{R}\right]\). From the Left over Hash lemma [29], distribution \(\left(\overline{\mathbf{A}},\overline{\mathbf{A}}\mathbf{R}\right)\) and distribution \(\left(\overline{\mathbf{A}},\overline{\mathbf{A}}\mathbf{R}\right)\) are statistically indistinguishable, for \(\mathbf{B}\in\mathbb{Z}_{q}^{n\times\mathrm{w}}\). Therefore, in the view of adversary \(\mathcal{A}\), the matrix in Game0 and in Game1 are statistically indistinguishable, and adversary \(\mathcal{A}\) cannot distinguish Game0 and Game1 with negligible advantages. **Game2** The difference between Game2 and Game1 is that Challenger \(\mathcal{C}\) changes the corresponding way to query \(id\
eq id^{*}\) secret key. Game2 uses **GenTrap** algorithm to generate matrix \(\mathbf{G}\) and lattice \(\Lambda_{q}^{\perp}(\mathbf{G})\) trapdoor matrix \(\mathbf{R}_{\mathbf{G}}\). Keeping the form of \(\mathbf{A}=\left[\overline{\mathbf{A}}\right]-\mathbf{H}_{id^{*}}\mathbf{G}-\overline{\mathbf{A}} \mathbf{R}\) in Game1. According to the definition of FRD encoding function, \((\mathbf{H}_{id}-\mathbf{H}_{id^{*}})\) is nonsingular. Challenger \(\mathcal{C}\) can respond to the secret key query of adversary \(\mathcal{A}\) through the trapdoor matrix \(\mathbf{R}_{\mathbf{G}}\) to sample the preimage. Run sampling algorithm \(\mathbf{t}_{id}\leftarrow\textbf{SampleD}(\mathbf{A}_{id},\mathbf{R}_{\mathbf{G}},\mathbf{u},\sigma)\) and output secret key \(\mathbf{s}_{id}=(1,-\mathbf{t}_{id})\) to adversary \(\mathcal{A}\). If \(id=id^{*}\), then \((\mathbf{H}_{id}-\mathbf{H}_{id^{*}})\) is a singular matrix, and the game ends. The distribution \(\mathcal{D}_{q(A_{id}),\sigma\omega(\sqrt{\log n})}\) of \(\mathbf{s}_{id}\) in Game2 and \(\mathbf{s}_{id}\) in Game2 with negligible advantages. **Game3** The difference between Game3 and Game2 is that the challenge ciphertext is always selected as a random independent element of \(\mathbb{Z}_{q}^{m^{\prime}}\) in the ciphertext space, so the advantage of adversary \(\mathcal{A}\) is zero. For PPT adversary \(\mathcal{A}\), it is still necessary to prove that the adversary cannot distinguish Game2 and Game3 in computation through the hardness of the LWE problem. Assuming adversary \(\mathcal{A}\) has non-negligible advantage in distinguishing Game2 and Game3, we use adversary \(\mathcal{A}\) to construct an LWE algorithm \(\mathcal{E}\). Recall from definition 5 that an LWE problem instance is provided as a sampling \(\mathcal{O}\) which can be either truly random \(\mathcal{O}_{\mathbf{5}}\) or noise pseudo-random \(\mathcal{O}_{\mathbf{s}}\). Challenger \(\mathcal{C}\) uses the adversary \(\mathcal{A}\) to distinguish the two.