Paper 2015/712

Adaptive Proofs have Straightline Extractors (in the Random Oracle Model)

David Bernhard, Bogdan Warinschi, and Ngoc Khanh Nguyen

Abstract

Abstract. The concept of adaptive security for proofs of knowledge was recently studied by Bernhard et al. They formalised adaptive security in the ROM and showed that the non-interactive version of the Schnorr protocol obtained using the Fiat-Shamir transformation is not adaptively secure unless the one-more discrete logarithm problem is easy. Their only construction for adaptively secure protocols used the Fischlin transformation [3] which yields protocols with straight-line extractors. In this paper we provide two further key insights. Our main result shows that any adaptively secure protocol must have a straight-line extractor: even the most clever rewinding strategies cannot offer any benefits against adaptive provers. Then, we show that any Fiat-Shamir transformed SIGMA-protocol is not adaptively secure unless a related problem which we call the SIGMA-one-wayness problem is easy. This assumption concerns not just Schnorr but applies to a whole class of SIGMA-protocols including e.g. Chaum-Pedersen and representation proofs. We also prove that SIGMA-one-wayness is hard in the generic group model. Taken together, these results suggest that Fiat-Shamir transformed SIGMA-protocols should not be used in settings where adaptive security is important.

Note: major revision - new author added

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
zero-knowledgesigma protocoladaptive securitymetareductiondiscrete logarithm
Contact author(s)
bernhard @ cs bris ac uk
History
2016-10-18: revised
2015-07-18: received
See all versions
Short URL
https://ia.cr/2015/712
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/712,
      author = {David Bernhard and Bogdan Warinschi and Ngoc Khanh Nguyen},
      title = {Adaptive Proofs have Straightline Extractors (in the Random Oracle Model)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/712},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/712}},
      url = {https://eprint.iacr.org/2015/712}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.