3
$\begingroup$

I have read that if the DDH problem could be efficiently solved, the IND-CPA would not hold for ElGamal.

I don't see why it makes ElGamal less secure if you have $g^a$, $g^b$ and $g^c$

$\endgroup$
3
$\begingroup$

Let $\mathcal{A}(g^a,g^b,g^c)$ be a DDH adversary which will return 1 if it thinks that $c = ab$, and return 0 if it thinks that $c$ is chosen from random.

Let $a$ is a private key and $g^a$ is a public key, we can attack IND-CPA of ElGamal encryption as follows.

  1. Random $m_0,m_1$ and send them to the challenger.
  2. The challenger will random $b$ and send $(g^b,g^{ab} m_i)$ back, where $i$ is the experiment number.
  3. We can call $\mathcal{A}(g^a,g^b,\frac{g^{ab}m_i}{m_0})$. If it returns 1, we will guess that we are in Experiment 0, but, if it returns 0, we will guess that we are in Experiment 1.

Now we can distinguish between Experiment 0 and Experiment 1 easily.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.