Paper 2020/915

Does Fiat-Shamir Require a Cryptographic Hash Function?

Yilei Chen, Alex Lombardi, Fermi Ma, and Willy Quach

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 about the interactive protocol (i.e., we invoke the generic group model), while in others, we argue soundness in the plain model. At a high level, the security of each resulting non-interactive protocol derives from hard problems already implicit in the original interactive protocol. On the other hand, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope that this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
fiat-shamir
Contact author(s)
chenyilei ra @ gmail com
alexjl @ mit edu
fermima @ alum mit edu
quach w @ husky neu edu
History
2021-02-24: revised
2020-07-23: received
See all versions
Short URL
https://ia.cr/2020/915
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/915,
      author = {Yilei Chen and Alex Lombardi and Fermi Ma and Willy Quach},
      title = {Does Fiat-Shamir Require a Cryptographic Hash Function?},
      howpublished = {Cryptology ePrint Archive, Paper 2020/915},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/915}},
      url = {https://eprint.iacr.org/2020/915}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.