7
$\begingroup$

We all know that textbook ElGamal falls due to chosen ciphertext attacks, because of its multiplicative homomorphic property ($E(A)*E(B)=E(AB)$).

However these attacks require the ciphertext ($E(A)$ or $E(B)$) to be given, meaning as per this answer this would mean ElGamal isn't IND-CCA2, but IND-CCA1 as the access to a decryption oracle before the ciphertext is known doesn't help anything.

Hence my question:
Is the ElGamal encryption scheme IND-CCA1 or "only" IND-CPA?

"Bonus" question:
If the ElGamal encryption scheme isn't IND-CCA1 how would the CCA1 attack look like?

$\endgroup$
1

1 Answer 1

10
$\begingroup$

The CCA1 security of ElGamal is a big open question. There are no attacks known, but standard reductions don't seem to work.

In 1991, Damgard proposed an ElGamal variant and proved it to be CCA1-secure (albeit under a very problematic non-falsifiable assumption, called the "knowledge of exponent assumption"); see the paper here http://link.springer.com/chapter/10.1007%2F3-540-46766-1_36.

More recently, Lipmaa here showed that ElGamal can be proven to be CCA1-secure under a non-standard (but falsifiable) assumption. The assumption is that DDH is hard even given access to a static CDH oracle (that computes the Diffie-Hellman function for a fixed "secret" exponent). [Caveat: I haven't read the paper so I can't vouch for correctness...]

$\endgroup$
1

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.