I understand that if DDH (Decisional Diffie–Hellman) is hard then ElGamal is CPA secure. But I'm having confusion on what part the DDH applies to.

So, given $pk=(G, g, y), y=g^x$ and $sk=(pk,x), x \leftarrow Z_q$

Encryption: pick random $r \leftarrow Z_q$ then $(u,v)=(g^r, y^rm)$

Decryption: $m=u^{-x}v$ because $u^{-x}v=(g^r)^{-x}y^rm=(g^x)^{-r}y^rm=(y)^{-r}y^r=m$

From here, it says that:

Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$

I'm not understanding where this is applied to. I think it is at the decryption part but have more confusion of whether it is a DDH or CDH problem. Could someone highlight which part the $g^a$, $g^b$ and $g^c$?


1 Answer 1


So let's go through the IND-CPA game, shall we?

  1. Pick two messages $m_0$ and $m_1$ arbitrarily.
  2. Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c=E(m_b)$.
  3. Output your guess for $b$ named $b'$. You "win" iff $b=b'$.

So you have two messages $m_0,m_1$, a ciphertext $c=(u,v)=(g^k,y^k\cdot m_b)=(g^k,g^{xk}\cdot m_b)$ and the public key $y=g^x$. Now note that you can calculate $c'=v\cdot m_0^{-1}$ which is $g^{xk}$ iff $b=0$. So what you now need to find out is whether $c'$ is the DH agreement of $u=g^k$ and $y=g^x$, which is precisely the DDH problem. If this is indeed this agreement then you know that $b=0$ and if not you know that $b=1$ and thus "win" the IND-CPA game.

  • $\begingroup$ The DH agreement of $u$ and $y$ is what I do not understand. So it returns $b=0$ if $c'=g^{xk}$ which is hard because... $\endgroup$
    – user153882
    Commented Dec 6, 2016 at 17:06
  • 1
    $\begingroup$ @user153882 deciding whether $c'=g^{xk}$ given $g^x,g^k,c'$ is precisely the DDH problem. $\endgroup$
    – SEJPM
    Commented Dec 6, 2016 at 17:11
  • 1
    $\begingroup$ Just for the record: this answer does not explain why “DDH is hard” implies “ElGamal is INC-CPA secure”, it goes the other direction. $\endgroup$
    – kirelagin
    Commented Apr 25, 2018 at 10:15
  • $\begingroup$ In the given IND-CPA game, how do you show the adversary's ability to query the encryption Oracle? $\endgroup$
    – Jeffrey
    Commented Apr 28 at 2:40

Your Answer

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

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