@inbook {19646,
title = {Why {\textquotedblleft}Fiat-Shamir for Proofs{\textquotedblright} Lacks a Proof},
booktitle = {Theory of Cryptography},
series = {Lecture Notes in Computer Science},
year = {2013},
month = {2013/01/01/},
pages = {182 - 201},
publisher = {Springer Berlin Heidelberg},
organization = {Springer Berlin Heidelberg},
abstract = {The Fiat-Shamir heuristic [CRYPTO {\textquoteright}86] is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover{\textquoteright}s first message to select the verifier{\textquoteright}s challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai [FOCS {\textquoteright}03] shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps we can securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if we must fail for some computationally sound arguments. Indeed, this has been conjectured to be the case by Barak, Lindell and Vadhan [FOCS {\textquoteright}03], but we do not have any provably secure instantiation under any {\textquotedblleft}standard assumption{\textquotedblright}. In this work, we give a broad black-box separation result showing that the security of the Fiat-Shamir heuristic for statistically sound proofs cannot be proved under virtually any standard assumption via a black-box reduction. More precisely: {\textendash}If we want to have a {\textquotedblleft}universal{\textquotedblright} instantiation of the Fiat-Shamir heuristic that works for all 3-message public-coin proofs, then we cannot prove its security via a black-box reduction from any assumption that has the format of a {\textquotedblleft}cryptographic game{\textquotedblright}. {\textendash}For many concrete proof systems, if we want to have a {\textquotedblleft}specific{\textquotedblright} instantiation of the Fiat-Shamir heuristic for that proof system, then we cannot prove its security via a black box reduction from any {\textquotedblleft}falsifiable assumption{\textquotedblright} that has the format of a cryptographic game with an efficient challenger.},
keywords = {Algorithm Analysis and Problem Complexity, Computation by Abstract Devices, Data Encryption, Systems and Data Security},
isbn = {978-3-642-36593-5, 978-3-642-36594-2},
url = {http://link.springer.com/chapter/10.1007/978-3-642-36594-2_11},
author = {Bitansky, Nir and Dana Dachman-Soled and Garg, Sanjam and Jain, Abhishek and Kalai, Yael Tauman and L{\'o}pez-Alt, Adriana and Wichs, Daniel},
editor = {Sahai, Amit}
}