Does Fiat-Shamir Require a Cryptographic Hash Function?

Does Fiat-Shamir Require a Cryptographic Hash Function?

Cybersecurity Seminars Online seminar
Thursday, 12 August 2021
3 pm - 4 pm (AEST)
Free

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.

Based on the joint work with Alex Lombardi, Fermi Ma, and Willy Quach. To appear at Crypto 2021.

About the speaker

Yilei Chen
Assistant Professor, Tsinghua University

Yilei Chen is an assistant professor at Tsinghua University IIIS. Before joining Tsinghua he was a researcher at VISA Research. In 2018 he got his Ph.D. from Boston University under the guidance of Professor Ran Canetti and Professor Leonid Reyzin. Yilei's research interest is in cryptography, especially in the areas of lattice and quantum computation.

Monash University values the privacy of every individual's personal information and is committed to the protection of that information from unauthorised use and disclosure except where permitted by law. For information about the handling of your personal information please see Data Protection and Privacy Procedure and the relevant Data Protection and Privacy Collection Statement that applies to you depending on the nature of your interaction with us.

If you have any questions about how Monash University is collecting and handling your personal information, please contact our Data Protection and Privacy Office at dataprotectionofficer@monash.edu.

Research

Event contact

Share this event