Adaptive Proofs of Knowledge in the Random Oracle Model

David Bernhard; Marc Fischlin; Bogdan Warinschi

doi:10.1007/978-3-662-46447-2_28

Adaptive Proofs of Knowledge in the Random Oracle Model

David Bernhard
, Marc Fischlin
, Bogdan Warinschi

Cryptography and Information Security

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

25 Citations (Scopus)

Abstract

We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results:

(1) Simulation-sound adaptive proofs exist.

(2) The “encrypt-then-prove” construction with a simulation-sound adaptive proof yields CCA security. This appears to be a “folklore” result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes.

(3) We show that the Fiat-Shamir transformed Schnorr protocol is not adaptively secure and discuss the implications of this limitation.

Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.

Original language	English
Title of host publication	Public-Key Cryptography - PKC 2015
Subtitle of host publication	18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings
Editors	Jonathan Katz
Publisher	Springer
Pages	629-649
Number of pages	21
ISBN (Electronic)	9783662464472
ISBN (Print)	9783662464465
DOIs	https://doi.org/10.1007/978-3-662-46447-2_28
Publication status	Published - 2015

Publication series

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

Access to Document

10.1007/978-3-662-46447-2_28

https://eprint.iacr.org/2015/648.pdf

Handle.net

Persistent link

Cite this

Bernhard, D., Fischlin, M., & Warinschi, B. (2015). Adaptive Proofs of Knowledge in the Random Oracle Model. In J. Katz (Ed.), Public-Key Cryptography - PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings (pp. 629-649). (Lecture Notes in Computer Science; Vol. 9020). Springer. https://doi.org/10.1007/978-3-662-46447-2_28

Bernhard, David ; Fischlin, Marc ; Warinschi, Bogdan. / Adaptive Proofs of Knowledge in the Random Oracle Model. Public-Key Cryptography - PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings. editor / Jonathan Katz. Springer, 2015. pp. 629-649 (Lecture Notes in Computer Science).

@inproceedings{a5607561f15f4b45b8f82c44887bd10f,

title = "Adaptive Proofs of Knowledge in the Random Oracle Model",

abstract = "We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results: (1) Simulation-sound adaptive proofs exist. (2) The “encrypt-then-prove” construction with a simulation-sound adaptive proof yields CCA security. This appears to be a “folklore” result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes. (3) We show that the Fiat-Shamir transformed Schnorr protocol is not adaptively secure and discuss the implications of this limitation. Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.",

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

year = "2015",

doi = "10.1007/978-3-662-46447-2\_28",

language = "English",

isbn = "9783662464465",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "629--649",

editor = "Jonathan Katz",

booktitle = "Public-Key Cryptography - PKC 2015",

address = "United States",

}

Bernhard, D, Fischlin, M & Warinschi, B 2015, Adaptive Proofs of Knowledge in the Random Oracle Model. in J Katz (ed.), Public-Key Cryptography - PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9020, Springer, pp. 629-649. https://doi.org/10.1007/978-3-662-46447-2_28

Adaptive Proofs of Knowledge in the Random Oracle Model. / Bernhard, David; Fischlin, Marc; Warinschi, Bogdan.
Public-Key Cryptography - PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings. ed. / Jonathan Katz. Springer, 2015. p. 629-649 (Lecture Notes in Computer Science; Vol. 9020).

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

TY - GEN

T1 - Adaptive Proofs of Knowledge in the Random Oracle Model

AU - Bernhard, David

AU - Fischlin, Marc

AU - Warinschi, Bogdan

PY - 2015

Y1 - 2015

N2 - We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results: (1) Simulation-sound adaptive proofs exist. (2) The “encrypt-then-prove” construction with a simulation-sound adaptive proof yields CCA security. This appears to be a “folklore” result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes. (3) We show that the Fiat-Shamir transformed Schnorr protocol is not adaptively secure and discuss the implications of this limitation. Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.

AB - We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results: (1) Simulation-sound adaptive proofs exist. (2) The “encrypt-then-prove” construction with a simulation-sound adaptive proof yields CCA security. This appears to be a “folklore” result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes. (3) We show that the Fiat-Shamir transformed Schnorr protocol is not adaptively secure and discuss the implications of this limitation. Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.

U2 - 10.1007/978-3-662-46447-2_28

DO - 10.1007/978-3-662-46447-2_28

M3 - Conference Contribution (Conference Proceeding)

SN - 9783662464465

T3 - Lecture Notes in Computer Science

SP - 629

EP - 649

BT - Public-Key Cryptography - PKC 2015

A2 - Katz, Jonathan

PB - Springer

ER -

Bernhard D, Fischlin M, Warinschi B. Adaptive Proofs of Knowledge in the Random Oracle Model. In Katz J, editor, Public-Key Cryptography - PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings. Springer. 2015. p. 629-649. (Lecture Notes in Computer Science). Epub 2015 Mar 17. doi: 10.1007/978-3-662-46447-2_28

Adaptive Proofs of Knowledge in the Random Oracle Model

Abstract

Publication series

Access to Document

Handle.net

Fingerprint

Cite this