For heuristically instantiating the random oracle (RO) in Fiat-Shamir transform, it suffices to use a sufficiently complex hash function such as SHA-$3$.
This is the so-called "Fiat-Shamir heuristic".
However, this approach is known to not be sound in general: there are examples of interactive protocols that are secure in the random-oracle model which become insecure when instantiated with any concrete hash function [CGH,GK].
An example of such an interactive argument can be found in [GK].
However, we are not aware of interactive proofs where the Fiat-Shamir heuristic fails.
In fact, for securely instantiating the Fiat-Shamir transform for interactive proofs, constructing a type of hash function called correlation-intractable hash function suffices.
To be more precise, to instantiate Fiat-Shamir for a (public-coin) interactive proof $\Pi$, one needs to construct a CIHF family $H_k$ for the "bad challenge" relation $R_\Pi$, where:
- a hash function family $H_k$ is correlation intractable for $R_\Pi$ if, for a random choice of $k$, it is hard to find $x$ such that $(x,H_k(x))\in R_\Pi$.
- the bad challenge relation $R_\Pi$ captures the verifier messages on which the (malicious) prover can cheat and hence $H_k$ essentially helps "evade" these bad challenges.
Sections 1.1 and 1.2 in [HLR] give a decent overview of previous works and a technical overview of bad challenges/correlation intractability, respectively.
Constructing such hash functions is an area of active research: there has been a flurry of recent works [CCH+,PS,JKKZ,HLR,...] which design CIHFs under standard assumptions for the interactive proof at hand. Some of the results are listed below:
- [PS] (building on [CCH+]) constructed a CIHF for the GMW protocol for graph colouring assuming LWE
- [JKKZ] constructed a CIHF for the celebrated sumcheck protocol assuming sub-exponential hardness of LWE
- [HLR] shows how to instantiate certain types of sigma protocols assuming LWE
CIHF, as a primitive, seems to be "different" from symmetric-key primitives such as OWF [M].
Known constructions rely on "structured" assumptions such as LWE and CDH.
[CCH+]: Canetti et al., Fiat-Shamir: from practice to theory. STOC 2019
[CGH]: Canetti, Goldreich and Halevi, The random oracle methodology, revisited, JACM'04.
[GK]: Goldwasser and Kalai, On the (In)security of the Fiat-Shamir Paradigm, FOCS'03.
[HLR]: Holmgren, Lombardi and Rothblum, Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge), STOC'21
[JKKZ]: Jawale et al., SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE, STOC'20
[M]: Mour, Correlation Intractability vs. One-wayness, ePrint'21
[PS]: Peikert and Shiehian, Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors, Crypto'19