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 impossibilityFiat-Shamir paradigmCS proofsfalsifiable assumptions
Contact author(s)
lopez @ cs nyu edu
History
2012-12-18: received
Short URL
https://ia.cr/2012/706
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.