# ElGamal with elliptic curves for security

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!!

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.

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