# Why doesn't the ability to sample a single random bit imply the construction of a random oracle?

I'm trying to understand exactly how the random oracle model differs from the standard model. In many proofs & applications there are some assumptions that some randomness is sampled (i.e. a bit $$b \leftarrow\{0,1\}$$).

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $$H:\{0,1\}^m \rightarrow \{0,1\}^n$$. Just sample $$n$$ bits for the output, and keep a log so that all future queries are consistent.

• The ‘random oracle model’ is not so much a model for a hash function, but more of a model for how adversaries are structured: in terms of an oracle for a hash function. Does crypto.stackexchange.com/a/68298 help? – Squeamish Ossifrage Nov 8 '19 at 2:22
• I may not have phrased my question precisely. Basically I mean why do we get to sample elements from a set uniformly at random in the standard model of computation? As in, where does the randomness 'come from' if not a random oracle? It seems to me that with the ability to sample a single bit comes the ability to simulate a random oracle. – Andy Dienes Nov 8 '19 at 2:28
• @AndyDienes ‘Security in the random oracle model’ or ‘ROM theorems’ are about transforming (say) a signature forger which takes as a parameter an oracle for the hash function, into an algorithm that (say) computes discrete logs, by constructing a specially crafted hash function that (a) has the correct distribution, but (b) does the bookkeeping to extract a discrete log out of whatever magic it is the forger is doing. That's why I say it's a model for adversaries more than just a model for hash functions. Did you try reading the answer I linked? – Squeamish Ossifrage Nov 8 '19 at 2:41
• For example, consider RSA-FDH with MD5 (with $\operatorname{MD5}(m)$ expanded into a full domain however you like). A signature is a bit string representing an integer $s$ such that $s^3 \equiv H(m) \pmod n$. A forger that is generic in terms of the hash function $H$ can be turned into an algorithm for computing cube roots modulo $n$ by feeding it a specially crafted hash function. But there's a forger that works without computing cube roots modulo $n$—instead, it exploits a collision in MD5. So it only works when the hash function is actually MD5—this forger is not a ROM adversary. – Squeamish Ossifrage Nov 8 '19 at 2:45
• @SqueamishOssifrage Ok, but drop all notions of adversarial models, security, and hash functions. On a very basic level, it seems to me that "access to a random bit" implies "access to a random function." I don't understand how some probabilistic Turing machine $\mathcal{A}$ is existentially different from $\mathcal{A}^H$ given access to a random function. – Andy Dienes Nov 8 '19 at 2:56

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $$H:\{0,1\}^m \rightarrow \{0,1\}^n$$. Just sample $$n$$ bits for the output, and keep a log so that all future queries are consistent.

Sure. You could design a signature scheme where there is a central party—a gnome sitting in a standard box flipping coins—and everyone on the planet has a telephone line directly to the gnome that cannot be intercepted so that everyone gets the same values from the gnome. That's not a particularly practical way to design a cryptosystem—we might like to be able to sign and verify messages offline, for example—but more importantly, it's not really what the random oracle model is about.

The random oracle model is not a just model for hash functions, but a model for adversaries. Let's take an example: in the signature game EUF-CMA—existential unforgeability under chosen-message attack—an adversary $$A$$ is by definition a random algorithm with access to a signing oracle and a public key: $$A(S, \mathit{pk})$$. The adversary wins if they can find any $$(m, \sigma)$$ pair that passes signature verification for any message $$m$$ they did not pass to the signing oracle $$S$$. This is sometimes called the ‘standard model’.

In the random oracle model, we consider a family of signature schemes indexed by a uniform random choice of function $$H$$. To make it clear that it depends on the hash function, we might label the signing oracle $$S_H$$. For example, in RSA-FDH signature, a public key is a large integer $$n$$ and a signature on a message $$m$$ is an integer $$\sigma$$ such that $$\sigma^3 \equiv H(m) \pmod n.$$ The signing oracle for a legitimate user is typically defined by $$S_H(m) := H(m)^d \pmod n,$$ where the secret exponent $$d$$ solves $$3d \equiv 1 \pmod{\lambda(n)}$$. Then, in the random oracle model, the adversary gets not just a signing oracle and public key as in $$A(S, n)$$ in the ‘standard model’, but also the hash oracle as in $$A(H, S_H, n)$$.

A ROM theorem is a statement of the following form:

• If there is a random algorithm $$A(H, S_H, n)$$ which, when $$H$$ is uniformly distributed, returns a forgery with high probability, then there is an algorithm $$A'(y, n)$$ which, when $$y$$ is uniformly distributed, returns a cube root of $$y$$ modulo $$n$$ with high probability.

The proof of the theorem is a definition of the algorithm $$A'$$, which constructs a hash oracle and signing oracle that have the correct distribution to fool the forger, but additionally do enough bookkeeping to extract a cube root out of whatever computations the forger does—without using the secret knowledge of $$d$$ that the legitimate user would have.

Obviously, internally the random algorithm $$A'$$ will involve flipping coins just like you described, to implement the hash oracle and the signing oracle. See my earlier ROM answer for details of the proof, and for more background, history, and literature references; see also the standard Bellare & Rogaway paper for the original proof of the RSA-FDH theorem in particular.

In other words, the random oracle model is an assumption about how adversaries are structured. Rather than using the somewhat confusing term ‘random oracle model’, some authors prefer to say that the theorem quoted above is simply a theorem about $$H$$-generic adversaries, meaning adversaries that are defined generically in terms of an arbitrary hash function rather than adversaries that exploit details of a particular hash function like collisions in MD5.

MD5-specific forgers have been exhibited, of course—for example, they figured prominently in an international incident of industrial sabotage by the United States and Israel against Iran—but they do not contradict this theorem, because such forgers only work with extremely low probability when $$H$$ is uniformly distributed. In other words, if an RSA-FDH signature scheme instantiated with MD5 goes bad, it's not because the fancy math of RSA-FDH went bad—rather, it's because MD5 went bad, and there's a good chance that using SHAKE128 instead will be fine.

• When the OP requests that you "drop all notions of adversarial models, security, and hash functions," this answer seems the very opposite. – Paul Uszak Nov 8 '19 at 23:50
• @PaulUszak I addressed the part about sampling bits—how, yes, it obviously is a thing you can do, but it's not really what the random oracle model is about. Satisfied? – Squeamish Ossifrage Nov 9 '19 at 2:45

So dropping "all notions of adversarial models, security, and hash functions", I see three problems with an application of a true random oracle. They revolve around Thomas Pornin's gnome and dice:-

1. Where does $$b$$ originate? An implemented function would be software obtaining access to a source of randomness, say $$\pi$$. A deterministic Turing machine is kinda deterministic. Therefore $$\pi$$ must be a PRNG seeded somehow, acting as a pseudo-gnome, not a real gnome. So we've already compromised and downgraded 'random' to 'pseudo-random'. This is a departure from your model, bringing with it all the constraints of pseudo-randomness.
2. If $$\pi$$ is a hardware source of random bits, then we need to start recording the inputs and outputs. This requires $$\mathcal{O}(2^m)$$ storage just for the inputs which quickly gets infeasible for the sizes of $$m$$ we commonly use these days. And similar storage of the $$\pi$$ outputs?
3. How would two implementations of such $$H$$ manage to inter-operate? The random oracle model is synthesized (loosely) in constructs which do productive stuff together. How would $$H^1$$ have access to the log from $$H^2$$? They'd be speaking in tongues.

It's tricky and thus true random oracles are hard/impossible in reality.

• This doesn't address the central point that the notion of an oracle is a way to model algorithms from complexity theory, not just a way to pick bits at random. – Squeamish Ossifrage Nov 8 '19 at 13:09
• @SqueamishOssifrage Well I thought that it was courteous to answer the question as posed rather than to make up my own. – Paul Uszak Nov 8 '19 at 23:44
• @SqueamishOssifrage Are you lot Andy? – Paul Uszak Nov 8 '19 at 23:44
• I don't know who or what a lot Andy is, but the central matter at hand is: ‘I'm trying to understand exactly how the random oracle model differs from the standard model.’ What you wrote doesn't even discuss the random oracle model except in name only. – Squeamish Ossifrage Nov 9 '19 at 2:47