# Proving the CCA-insecurity of El Gamal encryption scheme

I am trying to prove that El Gamal Encryption is not CCA-Secure.

If an adversary queried the encryption oracle for the encryption of $$m=1$$, he'll get a pair $$(c_1,c_2)=(g^y,g^{xy}\cdot m)=(g^y,g^{xy}\cdot 1)=(g^y,g^{xy}).$$ Then he could calculate $$g^{-xy}$$. Then he sends the challenger a pair $$(m_0,m_1)$$. When he gets the challenge ciphertext $$(c_1^*,c_2^*)$$ he can decrypt it and finds out which message has been encrypted. Hence, the adversary wins the experiment with non-negligible probability.

Does this prove make sense, or did I miss something?

Edit

This solution does not work since the value of y does not belong to the key, but it's generated randomly for every encryption.

A right solution would be as follows:

The adversary chooses some messages $$m_0=x\ and\ m_1=y$$. Then he sends these two messages $$(m_0,m_1)$$ to the challenger and get the encryption of one of them $$$$. Then he picks some z and multiplies it with the $$c_2$$ so he gets a new ciphertext $$$$. Then he queries the decryption oracle for the decryption of the new ciphertext. So, the resulting plaintext is either $$x . z$$ or $$y . z$$. Hence he can know which message has been encrypted.

• Welocme to Cryto.SE! Your proof doesn't quite work or at least it proves something else ;). Keep in mind that in ElGamal, $y$ is sampled at random for every new message. so after you ask for encryption of $1$, the next encryption will be $(g^{y'}, g^{xy'}*m)$. So as you've shown ElGamal would be insecure if we reused $y$. Aug 15, 2019 at 23:03
• Now on the question of proving IND-CCA (in)security, in the challenge phase you'll submit $(m_0, m_1)$ and receive $E(m_b), b \in \{0,1\}$. The idea is to used the decryption oracle to get the decryption of some crafted ciphertext $c'$ and use that to decide whether $b = 0$ or $b = 1$. Obviously $c'$ can be $E(m_b)$ , so the challenge is how can we make up a valid ciphertext? Aug 15, 2019 at 23:08
• Thanks for the answer. But in the CCA-security experiment for public key encryption schemes in "Introduction to modern cryptography", (sk,pk) <-- $Gen(1^{n})$ is called once at the begin of the experiment. and then the generated key will be used to encrypt and decrypt all messages in the experiment without picking a new y every time.That was the confusion :(.
– user63422
Aug 16, 2019 at 8:01
• The $key-gen$ algorithm is called once for sure but that algorithm generates $(x, g^x)$, where $x$ is the private key and $g^x$ the public key.But for encryption you still need to generate a new $y$ for encryption otherwise ElGamal would be completely insecure. In that case there's no point to really study CCA security since everyone could decrypt any ciphertext. Aug 16, 2019 at 8:33

No, as written, your technique doesn't work (as there's no specific reason why the encryption oracle use the same $$y$$ as the challenge ciphertext).
• He can multiply the challenge ciphertext with some value $x$. Then he can query the decryption oracle for the decryption of $c.x$ since this value has not been queried yet. I think I got it! thank you :)