Paper 2015/648

Adaptive Proofs of Knowledge in the Random Oracle Model

David Bernhard, Marc Fischlin, and Bogdan Warinschi

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in PKC 2015
Keywords
proofs of knowledgesigma protocolsschnorrfiat-shamirmetareduction
Contact author(s)
bernhard @ cs bris ac uk
History
2015-07-01: received
Short URL
https://ia.cr/2015/648
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/648,
      author = {David Bernhard and Marc Fischlin and Bogdan Warinschi},
      title = {Adaptive Proofs of Knowledge in the Random Oracle Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/648},
      year = {2015},
      url = {https://eprint.iacr.org/2015/648}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.