## 3 Conversion Method for CCA-Secure KEM
### Security Proof
In other words, the challenger always returns \(\mathsf{K}^{*}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) instead of computing \(\mathsf{K}^{*}=H_{2}(\mathsf{stmt}=(\mathsf{ct}^{*},k^{\prime}),\mathsf{com}=( \mathsf{com}_{\mathsf{sim}}^{\mathsf{ct}^{*}},\mathsf{com}_{\mathsf{sim}}^{k^ {\prime}}),\pi_{\mathsf{sim}}^{s}=(s,c))\). The adversary cannot distinguish Game 5 from Game 4 unless it queries the tuple \((\mathsf{stmt}=(\mathsf{ct}^{*},k^{\prime}),\mathsf{com}=(\mathsf{com}_{ \mathsf{sim}}^{\mathsf{ct}^{*}},\mathsf{com}_{\mathsf{sim}}^{k^{\prime}}), \pi_{\mathsf{sim}}^{*}=(s,c))\) to the \(H_{2}\) oracle. Note that \(k^{\prime}\) is a random key from \(\mathcal{A}\)'s view because \(\mathsf{ct}^{*}\) is independent of \(k^{\prime}\). Therefore, the probability that the adversary queries the tuple to the \(H_{2}\) oracle is at most \(1/|\mathcal{K}|\). Then, we have  
\[|\Pr[\mathsf{Win}_{5}]-\Pr[\mathsf{Win}_{4}]|\leq 1/|\mathcal{K}|.\]  
**Game 6. ** This game is identical to Game 5 except that the challenge ciphertext is computed differently. In the challenge phase, the challenger uses back \(k^{*}\) from \((\mathsf{ct}^{*},k^{*})\leftarrow\mathsf{KEM}.\mathsf{Encap}(\mathsf{pk};x)\). The other procedures are the same as in Game 5. Finally, it outputs \((\mathsf{CT}^{*},\mathsf{K}^{*})\). Like the case between Game 4 and Game 3, we can show that a distinguisher between Game 6 and Game 5 implies an adversary that breaks the IND-CPA security of the underlying \(\mathsf{KEM}\) scheme. For the sake of simplicity, we prove this later. Then, we have  
\[|\Pr[\mathsf{Win}_{6}]-\Pr[\mathsf{Win}_{5}]|\leq\epsilon_{\mathsf{IND-CPA}}^{ \mathsf{KEM}}.\]  
**Game 7. ** This game is identical to Game 6 except that the decapsulation query is operated differently. In this game, the challenger changes back the operation of the decapsulation query to normal. For a given ciphertext \(\mathsf{CT}=(\mathsf{ct},\pi=(s,c))\), the challenger computes \(\mathsf{k}\leftarrow\mathsf{KEM}.\mathsf{Decap}(\mathsf{sk},\mathsf{ct})\) using \(\mathsf{sk}\) and returns \(\mathsf{K}=H_{2}\big{(}\mathsf{stmt}=(\mathsf{pk},\mathsf{ct},\mathsf{k}), \mathsf{com}=(\mathsf{com}^{\mathsf{ct}},\mathsf{com}^{\mathsf{k}})\big{)}\) only if \(1\leftarrow\mathcal{V}^{H_{1}}(\mathsf{stmt},\pi)\) holds. Like the case between Game 3 and Game 2, an adversary cannot distinguish Game 7 from Game 6 unless it submits a ciphertext with a forged proof for a false statement. Then, by the simulation soundness of \(\mathsf{NIZK}\) with respect to \(q_{d}\) decapsulation queries, we have  
\[|\Pr[\mathsf{Win}_{7}]-\Pr[\mathsf{Win}_{6}]|\leq q_{d}\cdot\epsilon_{ \mathsf{SS}}.\]  
**Game 8**. : This game is identical to Game 7 except that the challenge ciphertext is computed differently. The challenger uses the real proving algorithm for \(\mathsf{NIZK}\) instead of using simulated proofs. Due to the zero-knowledge property of \(\mathsf{NIZK}\), we have  
\[|\Pr[\mathsf{Win}_{8}]-\Pr[\mathsf{Win}_{7}]|\leq\epsilon_{\mathsf{ZK}}.\]  
**Game 9**. : This game is identical to Game 8 but it does not abort when the event \(\mathsf{Coll}\) occurs during the simulation. Due to the collision resistance of the hash functions, we have  
\[|\Pr[\mathsf{Win}_{9}]-\Pr[\mathsf{Win}_{8}]|\leq\epsilon_{\mathsf{CR}}.\]  
Note that Game 9 is identical to the IND-CCA security game executed with \(b=0\). Then, we have  
\[|\Pr[\mathsf{Win}_{1}]-\Pr[\mathsf{Win}_{0}]|\leq\epsilon_{\mathsf{CR}}.\]0  
**Lemma 1**. : _If there exists a polynomial time distinguisher \(\mathcal{D}\) between Game 3 and Game 4, 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 Game 3 and Game 4. 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 3 with changes as follows.