## 5 Application
### CCA-Secure Elgamal Kem  
Let \(\mathsf{GGen}^{\mathsf{DDH}}(\lambda)\) be a group generator generating a group \(\mathcal{G}=(\mathbb{G},p,g)\), where the DDH assumption holds. In the Elgamal KEM, a public key consists of two group elements \((g,h=g^{x})\in\mathbb{G}^{2}\) with corresponding private key \(x\in\mathbb{Z}_{p}\). The encapsulation is done by computing \(\mathsf{ct}=g^{w}\in\mathbb{G}\) and \(\mathsf{k}=h^{w}\in\mathbb{G}\), and decapsulation is done by computing \(\mathsf{k}=(\mathsf{ct})^{x}\in\mathbb{G}\). Based on this scheme, the transformed IND-CCA-secure scheme is described as follows. **KEM.Gen(\(\lambda\))**: For a security parameter \(\lambda\), the setup algorithm proceeds as follows. 1. Generate \(\mathcal{G}=(\mathbb{G},p,g)\) by running \(\mathsf{GGen}(\lambda)\). 2. Choose a random exponent \(x\in\mathbb{Z}_{p}\) and set \(h=g^{x}\in\mathbb{G}\). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Game** & \(\mathsf{K}^{*}\) & \(\mathsf{stmt}^{*}\) & \(\mathsf{CT}^{*}\) & \(\mathsf{SK}\) & \(\mathsf{DecO}(\cdot)\) & **Property** \\ \hline
0 & \(H_{2}(\mathsf{stmt}^{*},\mathsf{com},\pi_{\mathsf{real}}^{*})\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{real}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & - \\
1 & \(H_{2}(\mathsf{stmt}^{*},\mathsf{com},\pi_{\mathsf{real}}^{*})\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{real}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & CR \\
2 & \(H_{2}(\mathsf{stmt}^{*},\mathsf{com},\pi_{\mathsf{sim}}^{*})\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & ZK \\
3 & \(H_{2}(\mathsf{stmt}^{*},\mathsf{com},\pi_{\mathsf{sim}}^{*})\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & - & R0 + SS & SS \\
4 & \(H_{2}(\mathsf{stmt}^{*},\mathsf{com},\pi_{\mathsf{sim}}^{*})\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{\prime})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & - & R0 + SS & IND-ID-CPA \\
5 & \(\mathsf{K}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{\prime})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & - & R0 + SS & \(1/|\mathcal{K}|\) \\
6 & \(\mathsf{K}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & - & R0 + SS & IND-ID-CPA \\
7 & \(\mathsf{K}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{sim}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & SS \\
8 & \(\mathsf{K}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{real}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & ZK \\
9 & \(\mathsf{K}\stackrel{{\mathsf{S}}}{{\leftarrow}}\{0,1\}^{\ell}\) & \((\mathsf{pp},\mathsf{ID}^{*},\mathsf{ct}^{*},k^{*})\) & \(\mathsf{ct}^{*},\pi_{\mathsf{real}}^{*}\) & \(\mathsf{sk}\) & \(\mathsf{IBKEM.Decap}(\cdot)\) & CR \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Values or operations of \(\mathsf{K}^{*}\), \(\mathsf{CT}^{*}\), \(\mathsf{SK}\), and \(\mathsf{DecO}(\cdot)\) in each game and properties ensuring the indistinguishability of consecutive games. \(\mathsf{RO}+\mathsf{SS}\) denotes that the simulator retrieves \(\mathsf{k}\) from a random oracle table and checks the validity of the ciphertext based on the SS property. Choose hash functions \(H_{1}:\{0,1\}^{*}\to\{0,1\}^{k}\subseteq\mathbb{Z}_{p}\) and \(H_{2}:\{0,1\}^{*}\to\{0,1\}^{\ell}\). Output \(\text{SK}=x\) and \(\text{PK}=(\mathbb{G},p,g,h,H_{1},H_{2})\). For a public key \(\text{PK}=(\mathbb{G},\,p,\,g,\,h,\,H_{1},\,H_{2})\), the Encap algorithm proceeds as follows.