A CCA Secure Hybrid Damgård's ElGamal Encryption
Yvo Desmedt and Duong Hieu Phan
Abstract:
ElGamal encryption, by its efficiency, is one of the most
used schemes in cryptographic applications. However, the original El-
Gamal scheme is only provably secure against passive attacks. Damgård
proposed a slight modification of ElGamal encryption scheme (named
Damgård's ElGamal scheme) that provides security against non-adaptive
chosen ciphertext attacks under a knowledge-of-exponent assumption.
Recently, the CCA1-security of Damgård's ElGamal scheme has been
proven under more standard assumptions.
In this paper, we study the open problem of CCA2-security of Damgard's
ElGamal. By employing a data encapsulation mechanism, we prove that
the resulted hybrid Damgard's ElGamal Encryption is secure against
adaptive chosen ciphertext attacks. The down side is that the proof of
security is based on a knowledge-of-exponent assumption. In terms of
efficiency, this scheme is more efficient (e.g. one exponentiation less in
encryption) than Kurosawa-Desmedt scheme, the most efficient scheme
in the standard model so far.
Ref: Proceeding of ProvSec '08, Lecture Notes in Computer Science Vol. 5324, pages 68-92, Springer-Verlag, 2008.
Available: pdf.