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 formats: PDF | BibTeX Citation Version: 20121218:130736 (All versions of this report) Discussion forum: Show discussion | Start new discussion