IACR News item: 18 July 2015
David Bernhard, Bogdan Warinschi
ePrint ReportRecent 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
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.
Additional news items may be found on the IACR news page.