1
$\begingroup$

I only know that ElGamal belongs to CPA based on DDH or CDH hard problem.

But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based?DLP?

ECC-ElGamal algorithm: ElGamal with elliptic curves

It would be better if there is a source of relevant literature!!! Thank you very much!!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based? DLP?

It's fairly easy to show that it is equivalent to the DDH problem.

Reducing CPA security to DDH:

Given a public key $aG$, and the possible encryption of a plaintext $P$, which is $X, Y$; if it is in fact ECC-ElGamal, then $X = bG, Y = abG + P$ for some random $b$.

Then we check whether $aG, X, Y-P$ is an DDH-triplet; it's easy to see that if we were given an ECC-ElGamal ciphertext, then it is.

Reducing DDH to CPA security:

Given a potential DDH-triplet $X, Y, Z$ (which is $aG, bG, abG$ if it is a triplet), then we select an arbitrary plaintext $P$, and pass to our CPA-oracle the public key $X$, and the ciphertext $Y, Z+P$; if it says that this is an El Gamal encryption, then we say that it is a DDH-triplet.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It's can't based on CDH hard problem? $\endgroup$
    – Hung LI
    May 5, 2021 at 13:04
  • $\begingroup$ @HungLI: see my last paragraph - if you have a DDH oracle, you can distinguish ECElGamal from random. $\endgroup$
    – poncho
    May 5, 2021 at 13:29

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.