It has long been known (Shoup and Gennaro 1998) that non-interactive proofs in the Random Oracle model that rely on rewinding extractors can be problematic.
Recent results by Seurin and Treger and Bernhard et al. formally confirmed such limitations for proofs derived from the Schnorr protocol via the Fiat-Shamir transform.
The limitations relate to the concept of adaptive proofs where an extractor needs to recover witnesses from proofs selected adaptively, as opposed to the standard setting where the extractor needs to work just for one proof.
Their main result is a separation between these two settings: under the one-more discrete log assumption, no efficient adaptive extractor can recover all witnesses from non-interactive Schnorr proofs (selected adaptively).
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
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
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.