International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 18 July 2015

David Bernhard, Bogdan Warinschi
ePrint Report ePrint Report
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

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.

Expand

Additional news items may be found on the IACR news page.