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

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

Paper 2012/706

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

Dana Dachman-Soled, Abhishek Jain, 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].

Metadata

Available format(s): PDF
Publication info: Published elsewhere. A merged version of this work and a work of [Bitansky, Garg, Wichs] will appear at TCC 2013
Keywords: black-box impossibility Fiat-Shamir paradigm CS proofs falsifiable assumptions
Contact author(s): lopez @ cs nyu edu
History: 2012-12-18: received
Short URL: https://ia.cr/2012/706
License: CC BY

BibTeX

@misc{cryptoeprint:2012/706,
      author = {Dana Dachman-Soled and Abhishek Jain and Yael Tauman Kalai and Adriana Lopez-Alt},
      title = {On the (In)security of the Fiat-Shamir Paradigm, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2012/706},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/706}},
      url = {https://eprint.iacr.org/2012/706}
}