Paper 2012/705

Why "Fiat-Shamir for Proofs" Lacks a Proof

Nir Bitansky, Sanjam Garg, and Daniel Wichs

Abstract

The Fiat-Shamir heuristic (CRYPTO '86) is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover's first message to select the verifier'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 '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 there exists a hash function that securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if it can fail for some computationally sound arguments. Indeed, the existence of such hash functions has been conjectured by Barak, Lindell and Vadhan (FOCS '03), who also gave a seemingly reasonable and sufficient condition under which such hash functions exist. However, we do not have any provably secure construction of such hash functions, under any standard assumption such as the hardness of DDH, RSA, QR, LWE, etc. In this work we give a broad black-box separation result, showing that the security of such hash functions cannot be proved under virtually any standard cryptographic assumption via a black-box reduction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. A merged version of this work and that of [Dachman-Soled, Jain, Kalai, Lopez-Alt] will appear at TCC 2013.
Keywords
interactive proofszero-knowledge
Contact author(s)
danwichs @ gmail com
History
2012-12-19: last of 2 revisions
2012-12-18: received
See all versions
Short URL
https://ia.cr/2012/705
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/705,
      author = {Nir Bitansky and Sanjam Garg and Daniel Wichs},
      title = {Why "Fiat-Shamir for Proofs" Lacks a Proof},
      howpublished = {Cryptology ePrint Archive, Paper 2012/705},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/705}},
      url = {https://eprint.iacr.org/2012/705}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.