On Limitations of the Fiat - Shamir Transformation.
David Bernhard, Bogdan Warinschi · 2015
It has long been known (Shoup and Gennaro 1998 [1]) that non-interactive proofs in the Random Oracle model that rely on rewinding extractors can be problematic. Recent results by Seurin and Treger [10] and Bernhard et al. [12] 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 Σ-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 Σ-one-wayness, says that a dishonest verifier in a single execution of an interactive Sigma protocol cannot recover the witness. This assumption is incomparable