Skip to content

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationApplied Cryptography and Network Security
Subtitle of host publication15th International Conference, ACNS 2017, Kanazawa, Japan, July 10-12, 2017, Proceedings
Publisher or commissioning bodySpringer
Pages336-353
Number of pages18
ISBN (Electronic)9783319612041
ISBN (Print)9783319612034
DOIs
DateAccepted/In press - 11 Apr 2017
DatePublished (current) - 26 Jun 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10355
ISSN (Print)0302-9743

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 [11] 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 -protocol is not adaptively secure unless a related problem which we call the -one-wayness problem is easy. This assumption concerns not just Schnorr but applies to a whole class of -protocols including e.g. Chaum-Pedersen and representation proofs. We also prove that -one-wayness is hard in an extension of the generic group model which, on its own is a contribution of independent interest. Taken together, these results suggest that the highly efficient proofs based on the popular Fiat-Shamir transformed -protocols should be used with care in settings where adaptive security of such proofs is important.

Download statistics

No data available

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Springer at https://link.springer.com/chapter/10.1007%2F978-3-319-61204-1_17. Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 537 KB, PDF-document

DOI

View research connections

Related faculties, schools or groups