Cryptology ePrint Archive: Report 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).

Category / Keywords: public-key cryptography / ElGamal encryption, Schnorr signature, chosen-ciphertext attacks, plaintext-aware encryption, robust encryption, hybrid encryption

Publication Info: This is the full version of a 16 page paper that appears at CT-RSA 2013

Date: received 14 Nov 2012, last revised 25 Feb 2013

Contact author: joanamarim at gmail com

Available format(s): PDF | BibTeX Citation

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.

Version: 20130225:070542 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]