In this paper we generalize, strengthen and extend these results. First we show that the above separation result holds for generic Sigma-protocols under the natural generalization of the one-more dlog assumption. Next, we strengthen the theorem by weakening the hypothesis. Our new assumption, which we call Sigma-one-wayness, says that a dishonest verifier in a single execution of an interactive Sigma protocol cannot recover the witness. This assumption is incomparable to zero-knowledge, as we will explain.
The main result of this paper clarifies the relation between adaptive proofs of knowledge (with rewinding) and other existing notions. Bernhard et al. introduced adaptive proofs as a new concept lying between proofs of knowledge (PoKs, with a rewinding extractor) and straight-line extractable proofs. They showed a separation between PoKs and adaptive proofs but left open the question whether adaptive proofs are always straight-line.
Our result implies that all adaptive proofs admit a straight-line extractor against the honest prover. This means that adaptive proofs are not a new class of proofs after all but simply another way to describe proofs with straight-line extractors.
Finally, we ask ourselves whether the result could be extended to a reduction to one-wayness of the function concerned — for Schnorr, this would mean solving the discrete logarithm (DLOG) problem. Our answer is negative: if there is any generic metareduction from adaptivity of Fiat-Shamir-Schnorr to DLOG then there is also a meta-metareduction breaking DLOG directly.
Category / Keywords: foundations / zero-knowledge, sigma protocol, adaptive security, metareduction, discrete logarithm Date: received 16 Jul 2015 Contact author: bernhard at cs bris ac uk Available format(s): PDF | BibTeX Citation Version: 20150718:125504 (All versions of this report) Short URL: ia.cr/2015/712 Discussion forum: Show discussion | Start new discussion