Cryptology ePrint Archive: Report 2012/706

On the (In)security of the Fiat-Shamir Paradigm, Revisited

Dana Dachman-Soled and Abhishek Jain and Yael Tauman Kalai and Adriana Lopez-Alt

Abstract: The Fiat-Shamir paradigm [CRYPTO'86] is a heuristic for converting 3-round identification schemes into signature schemes, and more generally, for collapsing rounds in public-coin interactive protocols. This heuristic is very popular both in theory and in practice, and many researchers have studied its security (and insecurity).

In this work, we continue this study. As our main result, we show that for many well studied interactive *proofs* (and arguments) the soundness of the Fiat-Shamir heuristic cannot be proven via a black-box reduction to any falsifiable assumption. Previously, the insecurity of this paradigm was exemplified only when applied to interactive arguments (as opposed to proofs).

Using similar techniques, we also show a black-box impossibility result for Micali's CS-proofs [FOCS'94]. Namely, we prove that there exist PCPs such that for "sufficiently hard'' NP languages, Micali's CS-proof cannot be proven sound via black-box reduction to any falsifiable assumption.

These results are obtained by extending the impossibility of two-message zero knowledge protocols due to Goldreich and Oren [J. Cryptology'94].

Category / Keywords: black-box impossibility, Fiat-Shamir paradigm, CS proofs, falsifiable assumptions

Publication Info: A merged version of this work and a work of [Bitansky, Garg, Wichs] will appear at TCC 2013

Date: received 17 Dec 2012

Contact author: lopez at cs nyu edu

Available format(s): PDF | BibTeX Citation

Version: 20121218:130736 (All versions of this report)

Short URL: ia.cr/2012/706

Discussion forum: Show discussion | Start new discussion