## 3 Conversion Method for CCA-Secure KEM
### Security Proof
* In the setup phase, \(\mathcal{A}\) sends \(\mathsf{PK}=(H_{1},H_{2},\mathsf{pk})\) to \(\mathcal{D}\). * In the challenge phase, the challenge ciphertext and key \((\mathsf{ct}^{*},k_{b}^{*})\) are given to \(\mathcal{A}\). Then, \(\mathcal{A}\) sets \(\mathsf{stmt}=(\mathsf{pk},\mathsf{ct}^{*},k_{b}^{*})\) and generates a simulated proof \(\pi_{\mathsf{sim}}^{*}\) on the statement \(\mathsf{stmt}\). \(\mathcal{A}\) sets \(\mathsf{K}^{*}=H_{2}(\mathsf{stmt},\mathsf{com}_{\mathsf{sim}},\pi_{\mathsf{ sim}}^{*})\), where \(\mathsf{com}_{\mathsf{sim}}\) is the deterministically computed commitment from \((\mathsf{stmt},\pi_{\mathsf{sim}}^{*})\). \(\mathcal{A}\) sends \((\mathsf{CT}^{*}=(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}),\mathsf{K}^{*})\) to \(\mathcal{D}\). In the guess phase, \(\mathcal{D}\) outputs its guess. If the guess is \"Game 3\", then \(\mathcal{A}\) outputs 1; otherwise, it output 0. Note that if \(b=1\), i.e., \(\mathsf{stmt}=(\mathsf{pk},\mathsf{ct}^{*},k_{b}^{*})\) is a true statement or \(\mathsf{stmt}=(\mathsf{pk},\mathsf{ct}^{*},k_{b}^{*})\in\mathcal{R}_{ \mathcal{L}}\), the above simulation is identical to Game 3 from \(\mathcal{D}\)'s viewpoint. Otherwise, the above simulation is identical to Game 4. Therefore, we have \[|\Pr[\mathsf{Win}_{1}]-\Pr[\mathsf{Win}_{0}]|\leq\epsilon_{\mathsf{CR}}.\]1  
**Lemma 2**. : _If there exists a polynomial time distinguisher \(\mathcal{D}\) between Games 5 and 6, then there exists a polynomial time adversary \(\mathcal{A}\) that breaks the IND-CPA security of KEM._  
Proof. : Let \(\mathcal{D}\) be a distinguisher between Games 5 and 6. Then, we show how to construct an \(\mathcal{A}\) that wins the IND-CPA security game of KEM using \(\mathcal{D}\) with the same advantage. \(\mathcal{A}\) receives a public key \(\mathsf{pk}\) as input. Then, \(\mathcal{A}\) runs \(\mathcal{D}\) by simulating Game 5 with changes as follows. * In the setup phase, \(\mathcal{A}\) sends \(\mathsf{PK}=(H_{1},H_{2},\mathsf{pk})\) to \(\mathcal{D}\). * In the challenge phase, the challenge ciphertext and key \((\mathsf{ct}^{*},k_{b}^{*})\) are given to \(\mathcal{A}\). Then, \(\mathcal{A}\) sets \(\mathsf{stmt}=(\mathsf{pk},\mathsf{ct}^{*},k_{b}^{*})\) and generates a simulated proof \(\pi_{\mathsf{sim}}^{*}\) on the statement \(\mathsf{stmt}\). Moreover, \(\mathcal{A}\) randomly chooses \(\mathsf{K}^{*}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) and sends \((\mathsf{CT}^{*}=(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}),\mathsf{K}^{*})\) to \(\mathcal{D}\). In the guess phase, \(\mathcal{D}\) outputs its guess. If the guess is \"Game 6\", then \(\mathcal{A}\) outputs 1; otherwise, it output 0. Note that if \(b=1\), i.e., \(\text{stmt}=(\text{pk},\text{ct}^{*},\text{k}_{b}^{*})\) is a true statement or \(\text{stmt}=(\text{pk},\text{ct}^{*},\text{k}_{b}^{*})\in\mathcal{R}_{\mathcal{L}}\), the above simulation is identical to Game 6 from \(\mathcal{D}\)'s viewpoint. Otherwise, the above simulation is identical to Game 5. Therefore, we have  
\[|\Pr[\mathsf{Win}_{1}]-\Pr[\mathsf{Win}_{0}]|\leq\epsilon_{\mathsf{CR}}.\]2  
This completes the proof of the theorem.