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 discuss the security of the ElGamal encryption scheme and its variant by Damgard. For the ElGamal encryption, we show that (1) under the generalized knowledge-of-exponent assumption and the one-more discrete log assumption, ElGamal encryption is one-way under nonadaptive chosen cipher attacks; (2) one-wayness of ElGamal encryption under non-adaptive chosen cipher attacks is equivalent to the hardness of one-more computational Diffie-Hellman problem. For a variant of ElGamal encryption proposed by Damgard (DEG), we give a new proof that DEG is semantically secure against non-adaptive chosen ciphertext attacks under the one-more decisional Diffie-Hellman assumption (although the same result for DEG security has been presented in the literature before, our proof is simpler). We also give a new security proof for DEG based on the decisional Diffie- Hellman assumption (DDHA) and a weaker version of the knowledge-of-exponent assumption (KEA), and note that KEA is stronger than necessary in the security proof of DEG, for which KEA was originally proposed.

Category / Keywords: public-key cryptography /

Date: received 7 May 2008

Contact author: j32wu at cs uwaterloo ca

Available formats: PDF | BibTeX Citation

Version: 20080512:202524 (All versions of this report)

Discussion forum: Show discussion | Start new discussion