Here in the proof of Elgemal one-wayness:

Consider an adversary V that can invert random Elgamal encryptions with $ε$ probability.

$V *$ : Adversary to compute the Diffie-Hellman function:
On input ($A = g^{a},B = g^{b}$), we must output $g^{ab}$.
Give $A$ to $V$ as the public key.
Pick a random $Z \in G$ and give $(B,Z)$ to $V$ as the ciphertext.
When $V$ outputs $m$, we output $Z / m$.

Note that the distribution $(A,(B,Z))$ does indeed correspond to a random Elgamal public key and encryption of a random message under that key.
Thus, with probability $ε$, $V$ outputs the "correct" plaintext $m$ (that is, $m$ such that $Z = mg^{ab}$). When this is the case, the output of $V^*$ matches the Diffie-Hellman function.
By our assumption that the CDH assumption holds for the underlying group, $ε$ must be negligible, as desired.

For the first CPA security proof described here, I think it makes adversary guess the value of $a$ or value of $b$. If it can guess one of those values, then it can know which message is encrypted ($m0$ or $m1$). Even it can guess one of those values, and decrypted plaintext is neither $m0$ nor $m1$, then it can know that $c$ is randomly generated. Is it right?

But in the second proof for one-wayness of encryption described above, as $Z$ value is selected randomly from $G.$ I can't catch the purpose of checking $Z = mg^{ab}$. Can anybody help me?


1 Answer 1


You are confusing two different security notions.

The proof you describe is regarding the Onewayness under chosen-plaintext attacks (OW-CPA). Basically, this notion covers the idea that it shouldn't be possible for an adversary to decrypt a given ciphertext (i.e., encryption is one-way), even if he can encrypt chosen plaintexts. As the proof shows, ElGamal is OW-CPA secure under the Computational Diffie-Hellman (CDH) assumption.

However, you are asking about indistinguishibility (i.e., guessing if an encryption is for one message or another). That's a different notion (and actually, a much more relevant one). It can be shown that ElGamal is IND-CPA secure under the Decisional Diffie-Hellman (DDH) assumption, which is weaker than CDH. Your understanding is correct: if an adversary can break OW-CPA, then it certainly can break IND-CPA. In security we are actually interested in the contrapositive: if a scheme is IND-CPA, then automatically is OW-CPA.

Regarding the OW-CPA proof of ElGamal, you have to know that in the OW security game, the adversary does not choose the underlying message, but the challenger. That means that the challenger doesn't even have to know the actual underlying message for the challenge ciphertext (that's why it can output a random $Z$ for the ciphertext).

Now, if an adversary can break OW-CPA, it means that he is capable to decompose $Z$ into $m$ and $g^{ab}$, in order to output $m$. The challenger then uses the result from the adversary to compute $g^{ab}$ as $Z/m$. Note that each time the adversary outputs a correct $m$ (which happens with probability $\epsilon$), the challenger succeeds in computing $g^{ab}$, since for each random $Z$, there is always one $m$ such that $Z = m g^{ab}$.

  • $\begingroup$ @cygnusv.Adversary is able to decrypt(break the security) if it can know value of $g^{ab}$. In this way, he can know $m$ and $mg^{ab}$ that is equal to Z. For security break, probability of adversary is defined as ε. If ε is negligible, it is safe.I understand now according to your explanation. Is it right? $\endgroup$
    – myat
    Commented Jul 14, 2016 at 8:17
  • $\begingroup$ Yes. The important idea is that if such adversary exists, then we could use it to break the CDH assumption (which we believe is hard). $\endgroup$
    – cygnusv
    Commented Jul 14, 2016 at 8:19
  • $\begingroup$ @cygnusv.In CDH assumption, finding $g^{ab}$ is hard when given $g,g^{a},g^{b}$. Therefore, the probability of adversary to break the security $\epsilon$ is negligible as finding $g^{ab}$ is hard. Limitation of adversary ability with CDH assumption. Is it right? $\endgroup$
    – myat
    Commented Jul 14, 2016 at 8:24
  • $\begingroup$ The proof shows that the probability of breaking CDH is equal to the probability of the adversary breaking OW-CPA, which in both cases is $\epsilon$. $\endgroup$
    – cygnusv
    Commented Jul 14, 2016 at 8:27

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.