Cryptology ePrint Archive: Report 2008/200

On The Security of The ElGamal Encryption Scheme and Damgard’s Variant

J. Wu and D.R. Stinson

Abstract: In this paper, we give security proofs for ElGamal encryption scheme and its variant by Damgard (DEG). For the ElGamal encryption, we show that (1) under the delayed-target discrete log assumption and a variant of the generalized knowledge-of-exponent assumption, ElGamal encryption is one-way under non-adaptive chosen cipher attacks; (2) one-wayness of ElGamal encryption under non-adaptive chosen cipher attacks is equivalent to the hardness of the delayed-target computational Diffie-Hellman problem. For DEG, (1) we give a new proof that DEG is semantically secure against non-adaptive chosen ciphertext attacks under the delayed-target decisional Diffie-Hellman assumption (although the same result has been presented in the literature before, our proof seems simpler); (2) we show that the DHK1 assumption, which was first proposed for DEG security proof, is stronger than necessary. A decisional (thus weaker) version of DHK1 assumption is sufficient for DEG security proof.

Category / Keywords: public-key cryptography /

Date: received 7 May 2008, last revised 16 Jul 2009

Contact author: j32wu at cs uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20090716:170720 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]