# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 5 Multi-Identity Full Homomorphic Encryption Scheme
### Security Analysis  
**Theorem 3**. : _Under the assumption that the \(LWE_{\lambda,\mathcal{Q},\mathcal{X}}\) assumption is hard, the WZ-MIBFHE scheme is IND-sID-CPA secure._  
Proof of Theorem 3.: The security of the WZ-MIBFHE scheme is established through an IND-sID-CPA game played between an adversary \(\mathcal{A}\) and a challenger \(\mathcal{C}\). The proof proceeds as follows:  
Suppose the adversary \(\mathcal{A}\) targets the identity \(id^{*}\), and let \(Adv[i]\) represent the adversary's advantage in game \(i\). **Game 0:** The standard IND-sID-CPA game in the WZ-MIBFHE scheme is conducted between the adversary \(\mathcal{A}\) and the challenger \(\mathcal{C}\). **Game 1:** The adversary \(\mathcal{A}\) declares the target identity \(id^{*}\). Compared to Game 0, the challenger \(\mathcal{C}\) changes the way the \(MPK\) matrix \(\mathbf{A}\) is generated in Game 1. A uniformly random matrix \(\mathbf{A}^{{}^{\prime\prime}}\) is generated, and \(MPK=(\mathbf{A}^{{}^{\prime\prime}},\mathbf{H})\). According to Lemma 3, for the adversary \(\mathcal{A}\), the matrix \(\mathbf{A}\) in Game 0 is statistically indistinguishable from the matrix \(\mathbf{A}^{{}^{\prime\prime}}\) in Game 1. Therefore, the advantage of the adversary \(\mathcal{A}\) in distinguishing Game 1 from Game 0 is negligible. **Game 2:** Compared to Game 1, the challenger \(\mathcal{C}\) changes the way public and private keys are generated in Game 2. In Game 2, a public matrix \(\mathbf{F}\) and a trapdoor matrix \(\mathbf{R}\) of the lattice \(\Lambda_{Q}^{\perp}(\mathbf{F})\) are generated. The adversary \(\mathcal{A}\) sends a set of identities \(\{id_{\alpha}\}_{\alpha\in\text{poly}(\lambda)}\) to the challenger \(\mathcal{C}\) for hash queries. The challenger \(\mathcal{C}\) chooses a uniformly random vector \(\mathbf{u}_{id_{\alpha}}^{\prime\prime}\) and sets \(\mathbf{A}_{id_{\alpha}}^{\prime\prime}=\left[\mathbf{u}_{id_{\alpha}}^{ \prime\prime}\right]\mathbf{A}^{\prime\prime}\). If the identity \(id^{*}\in\{id_{\alpha}\}_{\alpha\in\text{poly}(\lambda)}\), the game terminates. Otherwise, the challenge \(\mathcal{C}\) runs \(\mathbf{ApproxPreSamp}(\mathbf{A}_{id_{\alpha}}^{\prime\prime},\mathbf{R}, \mathbf{u}_{id_{\alpha}}^{\prime\prime},\mathbf{\sigma})\) to generate \(\mathbf{t}_{id_{\alpha}}^{\prime\prime}\), which satisfies \(\mathbf{A}_{id_{\alpha}}^{\prime\prime}\cdot\mathbf{t}_{id_{\alpha}}^{\prime \prime}=\mathbf{u}_{id_{\alpha}}^{\prime\prime}-\mathbf{e}_{app}\ mod\ Q\). Set \(\mathbf{sk}_{id_{\alpha}}^{\prime\prime}=(-1,\mathbf{t}_{id_{\alpha}}^{\prime \prime})\) and return it to the adversary \(\mathcal{A}\). The challenger \(\mathcal{C}\) ensures that \((id_{\alpha},\mathbf{u}_{id_{\alpha}}^{\prime\prime},\mathbf{t}_{id_{\alpha}} ^{\prime\prime})\in\) store is stored. Therefore, for the same identity \(id\), the adversary \(\mathcal{A}\) receives the same result for each query. Thus, the public and private keys in Game 2 and Game 1 are statistically indistinguishable. Consequently, the adversary \(\mathcal{A}\) is unable to differentiate between Game 2 and Game 1 within polynomial time with any significant advantage, i.e.,  
\[|\text{Adv}[2]-\text{Adv}[1]|=\text{negl}(\lambda)\]  
**Game 3:** The adversary \(\mathcal{A}\) chooses a pair of messages \((msg_{0},msg_{1})\) for the challenger \(\mathcal{C}\). The challenger \(\mathcal{C}\) generates extended ciphertexts in Game 3 differently than in Game 2. The challenger \(\mathcal{C}\) chooses a uniformly random matrix \(\hat{\mathbf{P}}\in\mathbb{Z}_{Q}^{Dm^{\prime}\times Dm^{\prime}\omega}\) and \(\hat{\mathbf{E}}\in\mathbb{Z}_{Q}^{Dm^{\prime}\times Dm^{\prime}\omega}\), generating the ciphertext \(\hat{\mathbf{C}}_{id^{*}}=\hat{\mathbf{P}}+msg_{\mathcal{C}}\mathbf{G}_{Dm^{ \prime}}+\hat{\mathbf{E}}\) for the message \(msg_{\mathcal{C}}\), where \(r\in\{0,1\}\), and sends the extended ciphertext \(\hat{\mathbf{C}}_{id^{*}}\) to the adversary \(\mathcal{A}\). **Lemma 5** ([25]): _Assuming the parameters satisfy the \(\text{LWE}_{\lambda,Q,\chi}\) hypothesis.