International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Does Fiat-Shamir Require a Cryptographic Hash Function?

Authors:
Yilei Chen , Tsinghua University
Alex Lombardi , MIT
Fermi Ma , Princeton and NTT Research
Willy Quach , Northeastern
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently unstructured'' (such as fixed-length SHA-2) should suffice. Finally, for some special interactive protocols, it is known how to (1) isolate a concrete security property of a hash function that suffices to instantiate Fiat-Shamir and (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors. In this work, we abandon this methodology and ask whether Fiat-Shamir truly requires a cryptographic hash function. Perhaps surprisingly, we show that in two of its most common applications --- building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-$p$ or bit decomposition. In some cases, we make idealized assumptions (i.e., we invoke the generic group model), while in others, we prove soundness in the plain model. On the negative side, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31132,
  title={Does Fiat-Shamir Require a Cryptographic Hash Function?},
  publisher={Springer-Verlag},
  author={Yilei Chen and Alex Lombardi and Fermi Ma and Willy Quach},
  year=2021
}