@inproceedings{11b9cb9cca3744db961d88ec2229ca3c,
title = "Adaptive Proofs Have Straightline Extractors (in the Random Oracle Model)",
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.",
author = "David Bernhard and Nguyen, {Ngoc Khanh} and Bogdan Warinschi",
year = "2017",
month = jun,
day = "26",
doi = "10.1007/978-3-319-61204-1_17",
language = "English",
isbn = "9783319612034",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "336--353",
booktitle = "Applied Cryptography and Network Security",
}