## 1 Introduction
### Flaw in Security Proof in Previous Research Literature  
The new conversion in [12] works correctly, but we have identified a flaw in its security analysis. For easier explanation, consider the ElGamal KEM as an underlying scheme. Let \(\mathbb{G}\) be a group of prime order \(p\), and let \((g^{w},h^{w})\) be a pair {ciphertext, key} for group elements \(g,h\in\mathbb{G}\), and a random \(w\in\mathbb{Z}_{p}\). It is easy to see that the pair can be an NIZK statement \(\text{stmt}=(g^{w},h^{w})\) for equality of discrete logarithms when the randomness \(w\) is the witness (i.e., NIZK-compatible). Let \(\mathsf{com}\) be a commitment \((g^{r},h^{r})\) for a random \(r\in\mathbb{Z}_{p}\). The Fiat-Shamir transform [13] gives the NIZK proof \(\pi=(c,s)\), where \(s=r+cw\in\mathbb{Z}_{p}\) and \(c=H_{1}(\text{stmt},\mathsf{com})\). Assuming that the hash function \(H_{1}\) is modeled as a random oracle, the NIZK proof system is proven to be honest verifier zero-knowledge and sound. The concept behind the transformation proposed in [12] is to see the original ElGamal KEM as a designated verifier proof system by setting \(h=g^{x}\) for a secret \(x\) (only known to the verifier) so that the element \(A_{1}=g^{w}\) is sufficient for the designated verifier NIZK statement. In the transformed variant of the ElGamal KEM, the resulting ciphertext consists of \((A_{1},\pi=(c,s))\), and the decapsulation algorithm (as a designated verifier) first recovers \(A_{2}=h^{w}\) by computing \((g^{w})^{x}\) and then computes \(\mathsf{com}=(g^{s}A_{1}^{-c},h^{s}A_{2}^{-c})\) along with \(\text{stmt}=(g^{w},h^{w})\) and \(\pi\). It also verifies that \(\pi\) is a valid proof for the recovered statement \(\text{stmt}\). If \(\pi\) is valid, the decapsulation algorithm computes the final KEM key as \(\mathsf{key}=H_{2}(\text{stmt},\mathsf{com},\pi)\) for another hash function \(H_{2}\). [PERSON] et al. [12] demonstrated that the above variant of the ElGamal KEM is tightly CCA-secure based on the _computational_ Diffie-Hellman (CDH) assumption. From a theoretical viewpoint, the first challenge in their security analysis is how to handle decapsulation queries issued by an adversary without knowing the secret key \(x\). Let \(\mathsf{CT}=(A_{1},\pi=(c,s))\) be a queried ciphertext, and let \(H_{1}\), \(H_{2}\) be modeled as random oracles. A reduction algorithm (simulator) finds a tuple in the \(H_{1}\) query table such that \(c=H_{1}(A_{1},\star,\star,\star)\), say \(c=H_{1}(A_{1},A_{2},B_{1},B_{2})\), and checks that \(\pi\) is the valid NIZK proof for the statement \((A_{1},A_{2})\) and the commitment \((B_{1},B_{2})\). If so, the simulator outputs the key \(\mathsf{key}=H_{2}(A_{1},A_{2},B_{1},B_{2},\pi)\) from the \(H_{2}\) query table. The decapsulation works correctly because of the soundness of the underlying NIZK proof system, meaning that the adversary is forced to generate the proof \(\pi\) for the well-formed ciphertext such that \(\log_{g}A_{1}=\log_{h}A_{2}\). The second challenge in their security analysis is to find the correct solution \(h^{a}\) to a given CDH instance \((g,g^{a},h)\) without security loss. The strategy in [12] is as follows: by using the zero-knowledge property, the simulator first generates a simulated proof \(\pi^{*}=(c^{*},s^{*})\) with respect to the element \(A_{1}^{*}=g^{a}\) for some unknown \(a\in\mathbb{Z}_{p}\) and implicitly sets \(c^{*}=H_{1}(A_{1}^{*},\circ,B_{1}^{*},\circ)\) and \(\mathsf{key}^{*}=H_{2}(A_{1}^{*},\circ,B_{1}^{*},\circ,\pi^{*})\), where \"\(\circ\)\" and \"\(\circ\)\" indicate that the simulator does not know the entries. After the challenge ciphertext \(\mathsf{CT}^{*}=(A_{1}^{*},\pi^{*}=(c^{*},s^{*}))\) and the challenge key \(\mathsf{key}^{*}\) are given to the adversary, the simulator waits for the adversary to query the hash inputs \((A_{1}^{*},\star,B_{1}^{*},\star,\pi^{*})\) for \(H_{2}\). [PERSON] et al.