How do you instantiate a Random Oracle?

I was recently discussing with a friend how to instantiate something that requires a RO (with a potentially long output) in a practical implementation. Specifically, for a Fiat-Shamir transform.

The options I see are:

1. Hash function
2. PRF
3. CSPRNG
4. KDF/randomness extractor
5. ...?

What primitive can be used, in what construction and what are arguments for its security?

For example, hash functions seem like a common choice but collision-resistance and pre-image resistance don't obviously map to random oracles. A hash function for which the output always starts with a 1 is an obvious counter-example with a trivial distinguisher. Practically, the confusion/diffusion make it sufficiently hard to control the output that in practice e.g. bitcoin mining is afaik just brute-force.

A CTR_DRBG (from NIST SP800-90A) with AES might also work. Since there is no seed involved, viewing it as a CSPRNG doesn't help. It's more the PRF properties that would be relevant, but how do those behave in CTR mode?

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