Paper 2012/649

A Robust and Plaintext-Aware Variant of Signed ElGamal Encryption

Yannick Seurin and Joana Treger

Abstract

Adding a Schnorr signature to ElGamal encryption is a popular proposal aiming at thwarting chosen-ciphertext attacks by rendering the scheme plaintext-aware. However, there is no known security proof for the resulting scheme, at least not in a weaker model than the one obtained by combining the Random Oracle Model (ROM) and the Generic Group Model (Schnorr and Jakobsson, ASIACRYPT 2000). In this paper, we propose a very simple modification to Schnorr-Signed ElGamal encryption such that the resulting scheme is semantically secure under adaptive chosen-ciphertext attacks (IND-CCA2-secure) in the ROM under the Decisional Diffie-Hellman assumption. In fact, we even prove that our new scheme is plaintext-aware in the ROM as defined by Bellare et al. (CRYPTO'98). Interestingly, we also observe that Schnorr-Signed ElGamal is not plaintext-aware (again, for the definition of Bellare et al.) under the Computational Diffie-Hellman assumption. We show that our new scheme additionally achieves anonymity as well as robustness, a notion formalized by Abdalla et al. (TCC 2010) which captures the fact that it is hard to create a ciphertext that is valid under two different public keys. Finally, we study the hybrid variant of our new proposal, and show that it is IND-CCA2-secure in the ROM under the Computational Diffie-Hellman assumption when used with a symmetric encryption scheme satisfying the weakest security notion, namely ciphertext indistinguishability under one-time attacks (IND-OT-security).

Note: Revised version of the paper including a modified definition of the main scheme---the scheme as previously defined was found out to be insecure---and additional detailed proofs.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. This is the full version of a 16 page paper that appears at CT-RSA 2013
Keywords
ElGamal encryptionSchnorr signaturechosen-ciphertext attacksplaintext-aware encryptionrobust encryptionhybrid encryption
Contact author(s)
joanamarim @ gmail com
History
2013-02-25: revised
2012-11-21: received
See all versions
Short URL
https://ia.cr/2012/649
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/649,
      author = {Yannick Seurin and Joana Treger},
      title = {A Robust and Plaintext-Aware Variant of Signed ElGamal Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/649},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/649}},
      url = {https://eprint.iacr.org/2012/649}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.