# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 3 Identity-Based Encryption Scheme
### Security Analysis  
**Theorem 2. **_The enhanced IBE scheme proposed in this paper is proven to be IND-sID-CPA secure under the assumption that the LWE\({}_{\lambda,Q,\lambda}\) problem is hard._  
Proof of Theorem 2. ** The security proof for the enhanced IBE scheme involves a sequence of IND-sID-CPA games conducted between the adversary \(\mathcal{A}\) and the challenger \(\mathcal{C}\) within the standard model. In this paper, we use the term \"game\" to describe the interaction process between the attacker and the encryption system, rather than referring to an actual game. The proof process is summarized as follows:  
**Game 0:** The initial standard IND-sID-CPA game between the adversary \(\mathcal{A}\) and the challenger \(\mathcal{C}\) for the IBE scheme. **Game 1:** The adversary \(\mathcal{A}\) declares the target identity \(id^{*}\) to be attacked. Compared to Game 0, the challenger \(\mathcal{C}\) in Game 1 changes the generation method of the matrix \(\mathbf{A}\), uniformly randomly generating the matrix  
\[\mathbf{A}=\left[\bar{\mathbf{A}}\parallel-\mathbf{H}_{id^{*}}\mathbf{F}-\bar {\mathbf{A}}\mathbf{R}\right]\]  
instead of  
\[\mathbf{A}=\left[\bar{\mathbf{A}}\parallel\mathbf{H}_{id}\mathbf{F}-\bar{ \mathbf{A}}\mathbf{R}\right]\]  
in Game 0. According to Lemma 3, for the adversary \(\mathcal{A}\), the matrix \(\mathbf{A}\) generated in Game 0 is statistically indistinguishable from the matrix \(\mathbf{A}\) generated in Game 1. Therefore, the ability of adversary \(\mathcal{A}\) to distinguish between Game 1 and Game 0 is extremely limited, with an advantage so small it can be considered negligible. **Game 2:** In Game 2, compared to Game 1, the challenger \(\mathcal{C}\) changes the response method for private key queries for \(id\
eq id^{*}\). Game 2 uses the public matrix \(\mathbf{F}\) and the trapdoor matrix \(\mathbf{R}\) of the lattice \(\Lambda_{Q}^{\perp}(\mathbf{F})\), retaining the form of  
\[\mathbf{A}=\left[\bar{\mathbf{A}}\parallel-\mathbf{H}_{id^{*}}\mathbf{F}-\bar {\mathbf{A}}\mathbf{R}\right]\]  
from Game 1, then  
\[\mathbf{A}_{id}=\left[\bar{\mathbf{A}}\parallel(\mathbf{H}_{id}-\mathbf{H}_{ id^{*}})\mathbf{F}-\bar{\mathbf{A}}\mathbf{R}\right].\]  
Based on the definition of the identity encoding FRD function, \((\mathbf{H}_{id}-\mathbf{H}_{id^{*}})\) is guaranteed to be non-singular. To respond to the adversary's private key query, the challenger utilizes preimage sampling on the trapdoor matrix \(\mathbf{R}\) by executing the preimage sampling algorithm  
\[\mathbf{ApproxPreSamp}(\mathbf{A}_{id},\mathbf{R},\mathbf{u},\sigma)\to \mathbf{t}_{id},\]  
and the private key \(\mathbf{sk}_{id}=(1,-\mathbf{t}_{id})\) is provided to the adversary \(\mathcal{A}\). If \(id=id^{*}\), then \((\mathbf{H}_{id}-\mathbf{H}_{id^{*}})\) becomes a singular matrix, causing the game to terminate. According to Lemma 4, the distribution \(\mathbf{sk}_{id}\) in Game 2 is statistically indistinguishable from \(\mathbf{sk}_{id}\) in Game 1 as \(\mathcal{D}_{\Lambda_{Q}^{\perp}(\mathbf{A}_{id}),\sigma\omega(\sqrt{\log n})}\). Therefore, the advantage of the adversary \(\mathcal{A}\) in distinguishing Game 2 from Game 1 is negligible. **Game 3:** Compared to Game 2,the challenger \(\mathcal{C}\) always selects random independent elements from the ciphertext space \(\mathbb{Z}_{Q}^{n^{\prime}}\) as the challenge ciphertext. Thus, the challenge ciphertext appears as an indistinguishable random ciphertext within the ciphertext space, making the adversary's advantage negligible. For the PPT adversary \(\mathcal{A}\), we still need to use the hardness of the \(LWE_{\lambda,\mathcal{O},\mathcal{X}}\) assumption to prove that the adversary cannot computationally distinguish Game 2 from Game 3. Suppose the adversary \(\mathcal{A}\) has a non-negligible advantage in distinguishing Game 2 from Game 3.