Does Fiat-Shamir Require a Cryptographic Hash Function?

Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
PublisherSpringer Science and Business Media Deutschland GmbH
Pages334-363
Number of pages30
ISBN (Print)9783030842581
DOIs
StatePublished - 2021
Externally publishedYes
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: Aug 16 2021Aug 20 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12828 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online
Period8/16/218/20/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Does Fiat-Shamir Require a Cryptographic Hash Function?'. Together they form a unique fingerprint.

Cite this