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
-
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},
url = {https://eprint.iacr.org/2012/706}
}
