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

David Bernhard, Ngoc Khanh Nguyen, Bogdan Warinschi

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

3 Citations (Scopus)
249 Downloads (Pure)

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.
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
PublisherSpringer
Pages336-353
Number of pages18
ISBN (Electronic)9783319612041
ISBN (Print)9783319612034
DOIs
Publication statusPublished - 26 Jun 2017

Publication series

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

Fingerprint

Dive into the research topics of 'Adaptive Proofs Have Straightline Extractors (in the Random Oracle Model)'. Together they form a unique fingerprint.

Cite this