On the Hardness of Proving CCA-Security of Signed ElGamal

David Bernhard; Marc Fischlin; Bogdan Warinschi

doi:10.1007/978-3-662-49384-7_3

On the Hardness of Proving CCA-Security of Signed ElGamal

David Bernhard, Marc Fischlin, Bogdan Warinschi

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

10 Citations (Scopus)

371 Downloads (Pure)

Abstract

The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide evidence that proving Signed ElGamal to be CCA secure in the random oracle model is hard. That is, building on previous work of Shoup and Gennaro (Eurocrypt'98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.

Original language	English
Title of host publication	Public-Key Cryptography – PKC 2016
Subtitle of host publication	19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I
Editors	Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang
Publisher	Springer
Pages	47-69
Number of pages	23
ISBN (Electronic)	9783662493847
ISBN (Print)	9783662493830
DOIs	https://doi.org/10.1007/978-3-662-49384-7_3
Publication status	Published - 18 Feb 2016
Event	PKC 2016 - , United Kingdom Duration: 6 Mar 2016 → …

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9614
ISSN (Print)	0302-9743

Conference

Conference	PKC 2016
Country/Territory	United Kingdom
Period	6/03/16 → …

Access to Document

10.1007/978-3-662-49384-7_3

David_Bernhard_pkc2016_submission
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-49384-7_3
Accepted author manuscript, 362 KB

Handle.net

Persistent link

Cite this

Bernhard, D., Fischlin, M., & Warinschi, B. (2016). On the Hardness of Proving CCA-Security of Signed ElGamal. In C.-M. Cheng, K.-M. Chung, G. Persiano, & B.-Y. Yang (Eds.), Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I (pp. 47-69). (Lecture Notes in Computer Science; Vol. 9614). Springer. https://doi.org/10.1007/978-3-662-49384-7_3

Bernhard, David ; Fischlin, Marc ; Warinschi, Bogdan. / On the Hardness of Proving CCA-Security of Signed ElGamal. Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. editor / Chen-Mou Cheng ; Kai-Min Chung ; Giuseppe Persiano ; Bo-Yin Yang. Springer, 2016. pp. 47-69 (Lecture Notes in Computer Science).

@inproceedings{69c5ebc18ddd4019a32fa41a68bd6407,

title = "On the Hardness of Proving CCA-Security of Signed ElGamal",

abstract = "The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide evidence that proving Signed ElGamal to be CCA secure in the random oracle model is hard. That is, building on previous work of Shoup and Gennaro (Eurocrypt'98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.",

author = "David Bernhard and Marc Fischlin and Bogdan Warinschi",

year = "2016",

month = feb,

day = "18",

doi = "10.1007/978-3-662-49384-7_3",

language = "English",

isbn = "9783662493830",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "47--69",

editor = "Chen-Mou Cheng and Kai-Min Chung and Giuseppe Persiano and Bo-Yin Yang",

booktitle = "Public-Key Cryptography – PKC 2016",

note = "PKC 2016 ; Conference date: 06-03-2016",

}

Bernhard, D, Fischlin, M & Warinschi, B 2016, On the Hardness of Proving CCA-Security of Signed ElGamal. in C-M Cheng, K-M Chung, G Persiano & B-Y Yang (eds), Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9614, Springer, pp. 47-69, PKC 2016, United Kingdom, 6/03/16. https://doi.org/10.1007/978-3-662-49384-7_3

On the Hardness of Proving CCA-Security of Signed ElGamal. / Bernhard, David; Fischlin, Marc; Warinschi, Bogdan.
Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. ed. / Chen-Mou Cheng; Kai-Min Chung; Giuseppe Persiano; Bo-Yin Yang. Springer, 2016. p. 47-69 (Lecture Notes in Computer Science; Vol. 9614).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - On the Hardness of Proving CCA-Security of Signed ElGamal

AU - Bernhard, David

AU - Fischlin, Marc

AU - Warinschi, Bogdan

PY - 2016/2/18

Y1 - 2016/2/18

N2 - The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide evidence that proving Signed ElGamal to be CCA secure in the random oracle model is hard. That is, building on previous work of Shoup and Gennaro (Eurocrypt'98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.

AB - The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide evidence that proving Signed ElGamal to be CCA secure in the random oracle model is hard. That is, building on previous work of Shoup and Gennaro (Eurocrypt'98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.

UR - http://eprint.iacr.org/2015/649

U2 - 10.1007/978-3-662-49384-7_3

DO - 10.1007/978-3-662-49384-7_3

M3 - Conference Contribution (Conference Proceeding)

SN - 9783662493830

T3 - Lecture Notes in Computer Science

SP - 47

EP - 69

BT - Public-Key Cryptography – PKC 2016

A2 - Cheng, Chen-Mou

A2 - Chung, Kai-Min

A2 - Persiano, Giuseppe

A2 - Yang, Bo-Yin

PB - Springer

T2 - PKC 2016

Y2 - 6 March 2016

ER -

Bernhard D, Fischlin M, Warinschi B. On the Hardness of Proving CCA-Security of Signed ElGamal. In Cheng CM, Chung KM, Persiano G, Yang BY, editors, Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. Springer. 2016. p. 47-69. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-49384-7_3

On the Hardness of Proving CCA-Security of Signed ElGamal

Abstract

Publication series

Conference

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this