ElGamal against chosen ciphertext attacks

Question

In Hoffstein, Pipher, and Silverman's book An Introduction to Mathematical Cryptography, the authors make the following remark:

An attack in which Eve has access to an oracle that decrypts arbitrary ciphertexts is known as a chosen ciphertext attack. The preceding proposition shows that the ElGamal system is secure against chosen ciphertext attacks. More precisely, it is secure if one assumes that the Diffie–Hellman problem is hard.

where the "preceding proposition" is a walk-through of a proof that if one can decrypt ElGamal ciphertexts, then one can solve the Diffie-Hellman problem.

However, all the sources that I can find online (including several on this site) seem to make the opposite claim, that ElGamal is not secure against chosen ciphertext attacks. The errata for the book makes no mention of this passage. Is my understanding of the authors' statement flawed?

Answer 1

As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the challenge ciphertext and the encryption of some random message; the homomorphism ensures that $Enc(pk, m_b) \cdot Enc(pk, m') = Enc(pk, m_b \cdot m')$, and therefore, the decryption oracle cannot refuse to respond to the query since the input is different to the challenge; now the adversary only has to remove $m'$ to recover the challenge message.

Also, something worth mentioning is that the proof given in that book does not follow the traditional conventions for proofs in provable security. First, they are not defining the security goal explicitly (i.e., are they trying to prove one-wayness? indistinguishability? some other notion?). And second, usually proofs are constructed as a reduction to a hard problem; that is, these proofs aim to reach a contradiction by which, if the scheme is insecure, then you could solve the hard problem. These proofs follow this template:

1. Define a security goal (e.g., Indistinguishability (IND)) and an attack model (in this case, chosen ciphertext attacks). Together they form a security notion (e.g., IND-CCA).
2. Assume the existence of an adversary $\mathcal A$ that breaks the scheme under the security notion.
3. Simulate the environment of $\mathcal A$. That is, you explicitly construct the oracles required by the attack model. Usually, you need to somehow embed elements from the hard problem instance you want to solve (e.g., elements from a DH tuple $(g^a, g^b)$).
4. Prove that using $\mathcal A$ you could solve the hard problem.
5. Since the hard problem is assumed to be hard, we have reached a contradiction, so the initial assumption (i.e., the statement in step 2) is false, and the scheme is actually secure.

However, the proof given in the book is doing something different. It is first assuming that there exists a decryption oracle, and then proving that you could solve the DH problem using it. Since the DH is hard, then the initial assumption must be false. In this case, the initial assumption is that there exists a decryption oracle, but this does not prove at all that the scheme is secure under chosen-ciphertext attacks.

Answer 2

ElGamal is not secure against chosen-ciphertext attacks, and there is a trivial attack. This is incorrect.