3
$\begingroup$

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$?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\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 Dec 6 '16 at 17:06
  • 1
    $\begingroup$ @user153882 deciding whether $c'=g^{xk}$ given $g^x,g^k,c'$ is precisely the DDH problem. $\endgroup$ – SEJPM Dec 6 '16 at 17:11
  • $\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 Apr 25 '18 at 10:15

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.