IACR News item: 18 December 2012
Dana Dachman-Soled, Abhishek Jain, Yael Tauman Kalai, Adriana Lopez-Alt
ePrint ReportIn 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].
Additional news items may be found on the IACR news page.