5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Does this answer your question? crypto.stackexchange.com/q/31921/54184 $\endgroup$
    – forest ♦
    Jan 24 at 12:06
  • $\begingroup$ I had seen that but it's more about the theoretical reason why we cannot instantiate a random oracle instead of how to practically do it in spite of that. :) $\endgroup$
    – Elias
    Jan 24 at 13:35

2 Answers 2

Reset to default
7
$\begingroup$

You should use a modern hash function designed to be indistinguishable from a random oracle, such as SHA-3 for fixed/short output sizes and SHAKE for variable/long output sizes.

"Collision resistant hash function" is a weaker abstraction than "random oracle" so you're right that there are hash functions which are collision resistant but are not indistinguishable from random oracles.

Older hash functions are often not suitable for instantiating a random oracle. In particular Merkle-Damgård hashes like SHA-2 allow length extensions, which a random oracle and SHA-3 do not.

Many PRFs and CSPRNGs are unsuitable in theory and practice, since they rely on random secret keys, while a random oracle is an unkeyed function. For example AES is vulnerable to related key attacks, because it was never designed to support attacker influenced keys.

Unfortunately it is impossible for a real hash function to fully meet the requirements of a random oracle, because one of the properties of a random oracle is that there is no short algorithm implementing it, so we have to settle for getting as close as possible. But that's mostly an issue for researchers trying to build a better abstraction for hash functions, not for practical protocol design, so you can usually ignore this complication.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How is it evaluated if a hash function is indistinguishable from a RO? $\endgroup$
    – Elias
    Jan 25 at 7:43
  • $\begingroup$ @Elias part of the problem with research on this matter is that we don't have a good definition that lets us evaluate this question. For example SHA-3 is trivially distinguishable from a random oracle, because there is a deterministic algorithm that predicts what it will output - the SHA-3 algorithm. From a practical perspective, this is not an issue, since this fact is blindingly obvious to protocol designers, but it tells us that the definition we're using in theoretical treatments of this isn't sound, and we need better definitions - which we don't yet have. $\endgroup$
    – James_pic
    Jan 25 at 11:56
  • $\begingroup$ Theory aside, what can we do? Chapter 8 of keccak.team/files/CSF-0.1.pdf seems like an interesting discussion and indicates that cryptanalysis is the only answer. $\endgroup$
    – Elias
    Jan 25 at 15:04
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I was reading "Random Oracles are Practical". I especially enjoyed "Of course there are lots of other equally simple ways to instantiate a random oracle; this was only an example." $\endgroup$
    – Elias
    Jan 24 at 13:47
  • $\begingroup$ "However, this is not known to be sound in general" It is in fact (as you go on to describe) known not to be sound in general. $\endgroup$
    – Maeher
    Jan 24 at 14:44
  • $\begingroup$ Sorry, that was phrased wrong. $\endgroup$
    – ckamath
    Jan 24 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.