0
$\begingroup$

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?

Thanks in advance.

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 $<c_1,c_2>$. Then he picks some z and multiplies it with the $c_2$ so he gets a new ciphertext $<c_1, c_2 . z> $. 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Marc Ilunga
    Aug 15, 2019 at 23:03
  • $\begingroup$ 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? $\endgroup$
    – Marc Ilunga
    Aug 15, 2019 at 23:08
  • $\begingroup$ 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 :(. $\endgroup$
    – user63422
    Aug 16, 2019 at 8:01
  • $\begingroup$ 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. $\endgroup$
    – Marc Ilunga
    Aug 16, 2019 at 8:33

1 Answer 1

Reset to default
1
$\begingroup$

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).

You need a different approach. For one, the adversary doesn't need to depend on an encryption oracle; if he has the public key, then he can encrypt anything he wants. What he does need to do is use the decryption oracle (as that performs an operation that the adversary cannot do himself).

So, how can the adversary create a ciphertext which is not the same as the challenge ciphertext, but when submitted to the decryption oracle, would tell him the answer?

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 :) $\endgroup$
    – user63422
    Aug 16, 2019 at 20:49
  • $\begingroup$ @OmarRenawi: By George, I think you've got it! In fact, that is precisely the answer (with x fixed at 2) I wrote before I decided that having you figure out the answer would be a better lesson... $\endgroup$
    – poncho
    Aug 16, 2019 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.