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

J.  Wu; D. R.  Stinson

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): j32wu @ cs uwaterloo ca
History: 2009-07-16: revised; 2008-05-12: received; See all versions
Short URL: https://ia.cr/2008/200
License: CC BY

BibTeX

@misc{cryptoeprint:2008/200,
      author = {J.  Wu and D. R.  Stinson},
      title = {On The Security of The {ElGamal} Encryption Scheme and Damgard’s Variant},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/200},
      year = {2008},
      url = {https://eprint.iacr.org/2008/200}
}