This post is part of a survey I co-wrote with Erica Blum and Makana Castillo-Martin for a quantum computation class at the University of Maryland in Fall 2019.

In this post, we define the Random Oracle Model (ROM) and the Quantum ROM (QROM), and give some examples of their uses and their flaws. We show that the QROM is unsound in the same way that the ROM is, and we conclude that that’s OK.

§ Definitions and Notation

I really don’t know what background to assume, but to balance comprehensibility and length of post, I’ve just chosen the things that I had to remind myself about when writing this.

§ Turing Machines

You can imagine Turing Machines as abstract machines that run programs specified by some programming language. Like your computer!

§ Random Oracles

An oracle is an abstraction—a black box—which Turing Machines can query and get a response from. I say “black box” and not “Turing Machine program,” for example, because an oracle is not necessarily a program that can be written down. Rather, it is an abstraction whose inner workings we have no information about. So when we talk about an oracle behaving a certain way, we are describing what kinds of outputs it gives in response to certain inputs, not how the oracle functions internally. When we want to express that a Turing Machine $\mathcal{A}$ has access to an oracle $\mathcal{O}$, we write $\mathcal{A}^\mathcal{O}$. This means that $\mathcal{A}$ can call $\mathcal{O}(x)$ on any input $x$ it pleases.

Definition (informal): A random oracle in a cryptosystem is a publicly accessible oracle (i.e., all parties can query it) which produces random and consistent responses. “Random” means that, until the oracle is queried for the first time on a given input, every possible response is equally likely. “Consistent” means that $\mathcal{O}$ always returns the same value on a given input.

Notice that implementing a random oracle is hard. You would have to construct a table that contains the output for every possible input. This table would be massive, so when we have to simulate a random oracle in practice, we normally do all this on the fly. That is, for each new input, we generate a new random value and save it in a table along with the input. This way, the oracle can respond consistently to previously seen queries.

§ Turing Reductions

It’s worth it to go over the definition of Turing reduction here, because the purpose of the random oracle model is to permit reductions that were not previously possible (as far as we’re aware).

Definition: A Turing Reduction from problem $X$ to problem $Y$ is a Turing Machine $\mathcal{A}$ such that, if $\mathcal{A}$ is given access to a Turing Machine $\mathcal{Y}$ which solves $Y$, then $\mathcal{A}^\mathcal{Y}$ can efficiently1 solve $X$. We say “$X$ reduces to $Y$”, or “$X \leq Y$” if and only if such a machine $\mathcal{A}$ exists.

In this definition, we take “problem” to mean a question of the form “does this thing satisfy relation $R$” or “what is a thing that makes this satisfy relation $R$”. Examples are

• Given an integer $N$, what is a prime number that divides $N$? The relation here is $R = \{(N, p) : p \textrm{ prime} \wedge p \mid N \}$
• Given a polynomial $P$ and a value $x$, is $x$ a root of $P$? The relation here is $R = \{(P, x) : P(x) = 0\}$

§ The Random Oracle Model

The Random Oracle Model (introduced in 1993 by Bellare and Rogaway) was invented as a response to a schism in the cryptographic community in the 1990s: practitioners were implementing all kinds of cryptographic protocols which used hash functions, while theoreticians had no way of proving that these schemes were secure. The aim of the ROM was to bridge this gap by formalizing a small assumption that many were making anyway: hash functions appear to behave randomly. Actually describing what “appear to behave randomly” means is more of an exercise in philosophy than math, so we’ll leave that out.2 But the gist of the formalization is captured in the following definition:

Definition (informal): We say that $X$ reduces to $Y$ in the ROM if and only if there is a reduction from $X$ to $Y’$, where $Y’$ is the same problem as $Y$ but with every hash function replaced with a random oracle.

Take note of what is not being said: no claim is ever made that a reduction which holds in the ROM necessarily holds when hash functions are used instead of random oracles. Accordingly, and appropriately, the ROM is considered a heuristic for cryptosystems which use hash functions; it does not necessarily prove anything about the scheme with hashes. Rogaway and Bellare go out of their way to state precisely this in their introduction of the ROM:

In order to bring to practice some of the benefits of provable security, it makes sense to incorporate into our models objects which capture the properties that practical primitives really seem to possess, and view these objects as basic even if the assumptions about them are, from a theoretical point of view, very strong…We stress that the proof is in the random oracle model and the last step is heuristic in nature. It is a thesis of this paper that significant assurance benefits nonetheless remain.

Innumerably many cryptosystems have been proven secure in the ROM (where “proven secure” means “reduced from a problem believed to be hard”). The Fiat-Shamir Transform (which is most often used in the ROM) has, alone, probably been used to construct hundreds of cryptosystems. The argument for the ROM goes deeper, though. Koblitz and Menezes make a strong argument that, not only does the ROM allow us to prove schemes secure that are otherwise unprovably secure (e.g., the Full-Domain Hash signature scheme), but it also gives us constructions that are less brittle to misuse (avoiding things like the duplicate signature key selection attack in the GHR signature scheme).

All this is to say that, while the ROM is just a heuristic, it’s a really really useful one.

§ Hash Functions are not Random Oracles

Earlier I said that no claim is made that hash functions can be modeled as random oracles. And that’s good, because it turns out that it’s false. A neat way of proving this is to construct a digital signature algorithm which is secure in the ROM, but insecure under any choice of hash function. I’ll repeat that because this is really surprising: there is a signature scheme which is secure in the ROM, but completely insecure under ANY choice of hash function. As far as I can tell, the first example of such a scheme was given3 in 1998 by CGH, but I’d like to use a different example4 by HMR, which I think is a lot cleaner and which I’ll paraphrase and prove in this section.

Suppose there’s a secure signature scheme5 $\mathcal{S}$ with signature algorithm $\mathsf{Sign}_k(m)$ where $k$ is the signing key. We define a new signature scheme $\mathcal{Evil}$ with signing algorithm $\mathsf{EvilSign}^\mathsf{H}_k(m)$ which has access access to some oracle $\mathsf{H}$ (we’ll compare the case where $\mathsf{H}$ is an oracle $\mathcal{O}$ versus when it’s a hash function $f$). Denote the security parameter by $\lambda$. On input $m$, $\mathsf{EvilSign}^\mathsf{H}_k$ will calculate $b := \mathsf{D^H}(m)$, where $\mathsf{D}$ is an algorithm we’ll define in a second. If $b = 0$, then the algorithm returns $\mathsf{Sign}_k(m)$, otherwise, it does the completely insecure thing and returns $k$.

$\mathsf{D^H}(m)$ is the algorithm that we use to distinguish between random oracles and hash functions. It exploits the idea that a hash function has a representation as a program, whereas a random oracle needs a massive truth table in order to describe its behavior. $\mathsf{D^\mathsf{H}}$ will interpret its input $m$ as the description of a (Universal Turing Machine) program $\pi$. It then checks whether $\pi(i) = \mathsf{H}(i)$ for all $0 \leq i < 2|\pi|+\lambda$. If this equality fails for any $i$, then $\mathsf{D}$ outputs 0. Otherwise, it outputs 1. We claim two things:

Claims:

1. If $\mathsf{H}$ is a hash function $f$, there exists an adversary that can always make $\mathsf{D}$ output 1.
2. If $\mathsf{H}$ is a random oracle $\mathcal{O}$, $\mathsf{D}$ outputs 0 with high probability (where the probability is taken over random choice of $\mathcal{O}$).

Proof of (I): This one’s easy: the adversary simply sends the encoding of $f$ itself. Then $\pi(i) = \mathsf{H}(i) = f(i)$ for all $i$.

Proof of (II): This can be proven by bounding the likelihood that there exists a program that can represent the truth table of $\mathcal{O}$. For a moment, let’s consider just programs of length at most $\ell$. Let $q_\ell = 2\ell+\lambda$.

The set of all outputs up to $q_\ell$ of all random oracles, pessimistically assuming that the oracles are binary-valued, is $\{(\mathcal{O}(1), \mathcal{O}(2), \ldots, \mathcal{O}(q_\ell)) : \mathcal{O} : \mathbb{N} \to \{0,1\}\}$. This set has size $2^{q_\ell}$. In comparison, consider the set of program outputs of programs of length at most $\ell$. Again, assume pessimistically that all programs of length at most $\ell$ halt and return binary values. Then the size of the set, $\{(\pi(1), \pi(2), \ldots, \pi(q_\ell)) : |\pi| \leq \ell\}$, is at most $2^{\ell+1}$. This is a much smaller set than that of the oracle outputs. So if $\mathcal{O}$ is chosen randomly, the likelihood that there exists a $\pi$ of length at most $\ell$ that describes $\mathcal{O}$ out to $q_\ell$ many places is

Then by the union bound, the probability $p$ that a random oracle has any program $\pi$ that agrees with it at the first $2|\pi| + \lambda$ values is

which is inverse-exponential in the security parameter.

If we are in the ROM, then it follows from claim (II) that the only way to construct a forgery in scheme $\mathcal{Evil}$ is to construct a forgery in $\mathcal{S}$. Since $\mathcal{S}$ is assumed to be secure against forgery, this is not possible. Thus, this scheme is secure in the ROM.

Further, it follows from claim (I) that for any choice of hash function $f$, $\mathsf{EvilSign}$ can be completely broken by an efficient adversary. Thus, we have constructed a scheme that is secure in the ROM and insecure under any choice of hash function!

§ Is the ROM Broken?

Given this ridiculous mismatch of security expectations, one may ask: is the ROM a reasonable heuristic to use if it so clearly fails to reflect reality in at least one cryptosystem? This is a matter of opinion.

The $\mathcal{Evil}$ cryptosystem above is a pathological example by any standard. The signature function is literally programmed to reveal the secret key some of the time. It turns out that weird examples like these are actually the only examples we have of the ROM failing to hold up in the real world. Further, there are a handful of examples where avoiding the ROM has actually introduced exploitable vulnerabilities into a cryptosystem6. These vulnerabilities normally arise from, in a broad sense, things having too much algebraic structure.

On the other hand, an unrealistic model is an unrealistic model. If there is a cryptosystem, albeit a contrived one, which serves as a counterexample to the claim that hash functions are interchangeable with random oracles, then why should we believe that there are some cryptosystems in which this claim is true?7 We don’t have any proofs so far of being able to model a hash function with a random oracle in a certain cryptosystem, only counterexamples.

I’ll hold off weighing in until the conclusion, but I think this is a reasonable question to ask, and not one that science or math can really answer. This is one of those cases where philosophy intersects cryptography in a way that can affect what people choose to research and how they construct their solutions.

§ The Quantum Random Oracle Model

It turns out that we have to go through this same moral conundrum when we talk about the QROM, because $\mathcal{Evil}$ is secure in the QROM too! Again, to be concrete, there is a signature scheme that is secure against quantum-capable adversaries in the QROM, but completely insecure for ANY choice of hash function. To get to this claim, we’ll need some of the basics of quantum computation theory.

§ A Quick Rundown of Quantum Computation

“Qubit” is a fancy term you might have heard before. A qubit is the most basic unit of data in Quantum Land, so it’ll be worth it to give a rigorous definition. First, we often fix the number of qubits in a system by fixing the dimension of the system. In particular, we say that a $b$-qubit system is a subset of $\mathbb{C}^{2^b} \cong \mathbb{C}^2 \otimes \cdots \otimes \mathbb{C}^2$ (tensored $b$ many times). A qubit is an element of the unit sphere $B = \{\|z\| = 1 : z \in \mathbb{C}^{2^b}\}$ (where the norm is the $L_2$ norm). The operations on qubits we care about are unitary operators, i.e., linear functions that preserve length, i.e., linear functions from $\mathbb{C}^{2^b}$ to $\mathbb{C}^{2^b}$ which map $B$ to $B$. We represent the $i$-th basis vector (0-indexed) of $\mathbb{C}^{2^b}$ by writing $\langle \mathsf{bin}(i)\rangle$, where $\mathsf{bin}(i)$ denotes the binary expansion of $i$.8 So for example, $\langle 000 \rangle$ denotes the 0-th basis vector of $\mathbb{C}^8$ (not the zero vector!), and $\langle 011 \rangle$ denotes the 3rd basis vector. Sometimes we will want to split up the basis vector label into two parts. To denote this, we say $\langle x,y \rangle = \langle x \| y\rangle$, i.e., the concatenation of the binary strings $x$ and $y$. For example, $\langle 001, 011 \rangle = \langle 001011 \rangle$.

Notice that the set of bitstrings of length $b$ is in bijection with the basis vectors of $\mathbb{C}^{2^b}$, so we can talk about “linear combinations of bitstrings” in a way that makes sense. For example, $v = (1/\sqrt{2})\cdot \langle 110 \rangle - (i/\sqrt{2})\cdot \langle 010\rangle$ is a vector in $B$. We say that this qubit $v$ represents a superposition of the bitstrings $\langle 110\rangle$ and $\langle 010\rangle$. This representation as the linear combination of bitstrings is unique for the same reason that the representation of a vector in terms of the standard basis is unique.

We can define linear operators that act on these bitstrings by defining mappings from basis elements to basis elements. For example, if $f$ is a function from $\{0,1\}^3$ to $\{0,1\}^3$ (i.e., bitstrings of length 3 to bitstrings of length 3), and $f(010) = 111$, then we can define a linear operator $F$ that takes $\langle 010\rangle$ to $\langle 111\rangle$. This gives a unitary operator whenever $f$ is a bijection on the bitstrings. But what if $f$ isn’t a bijection? What if $f(001) = f(010) = 111$? Then you can use a neat trick: define $F$ such that it takes the basis vector $\langle x, y \rangle$ to $\langle x, y \oplus f(x)\rangle$. This trick works because the output “remembers” the input, so the function is always invertible. For example,

Operators that are defined like this are almost always given $y = 0$. Finally, notice that we had to make the dimension of the space larger, and thus increase the number of qubits in our system in order to accommodate more bits. Indeed, doubling the dimension to account for non-injectivity of bit-valued functions is common practice.

Alright, that’s about all the background necessary to present the QROM and the final result.

§ Quantum Random Oracles

The QROM (introduced in 2010 by Boneh et al.) comes from a simple insight: if we believe that quantum computers could run hash function circuits in superposition (and we do), then why don’t we model hash functions as random oracles, but more quantum-y? This is, in essence, the same idea as the ROM, except the random oracles are allowed to be queried in quantum superposition. More specifically,

Definition: Given a random oracle $\mathcal{O}$, the associated quantum random oracle $\mathcal{O}_\mathrm{quant}$ is the unitary operator that maps a superposition of bitstrings to the superposition of its values when evaluated with $\mathcal{O}$. Concretely, for every basis vector $\langle x, y \rangle$, define

By this definition, $\mathcal{O}_\mathrm{quant}$ is a unitary operator, so it makes sense to say

Notice that a quantum random oracle is at least as powerful as a random oracle, since you can always query with the superposition of just a single value:

In fact, quantum random oracles are strictly more powerful than classical random oracles. Boneh et al. show a separation result. In particular, they present an identification scheme that is secure in the ROM, and insecure in the QROM.9

§ Quantum Hash Functions are not Quantum Random Oracles

Since the QROM is strictly more powerful than the ROM, it follows that QROM-security implies ROM-security. But we’d like to show that the ROM-secure $\mathcal{Evil}$ scheme above is also QROM-secure. Luckily, Boneh et al. also give us the conditions for when this converse statement is true.

Theorem: If a reduction to a problem $P$ holds in the ROM, and the reduction is history-free, then the reduction to problem $P$ holds in the QROM as well.

A history-free reduction is defined formally in the paper, but it suffices to say that a history-free reduction is a reduction that does not rewind its solver $\mathcal{Y}$, does not record the oracle queries, and does not modify oracle behavior based on previous queries.

Recall that the above proof of security in the ROM was actually a reduction to the security of the underlying hypothetical signature scheme $\mathcal{S}$. To prove QROM-security, we need to tweak the assumption a bit: instead of assuming that $\mathcal{S}$ is secure against classical adversaries, we need to further assume it is secure against quantum-capable adversaries. Admitting this, the only thing that needs to be shown is that the proof of ROM-security of $\mathcal{Evil}$ is history-free. Indeed, the reduction never recorded queries, rewound the solver, or modified its own behavior, so it’s pretty clear that it’s history free.10

§ Conclusions

And that’s it! We’ve just constructed a signature scheme (assuming the existence of a quantum-secure5 signature scheme) that is secure against quantum adversaries when modeling the hash functions as quantum-accessible random oracles, but is completely insecure under any choice of hash function!

I want to reiterate that the failure of the (Q)ROM to reflect real-world security should not necessarily be taken as a sign that we should stop using it, though some argue precisely that. My personal, highly unqualified opinion is that this construct has given us far more than it’s taken, and despite the fact that it sometimes fails to tell us something about our world, I am convinced, as Rogaway and Bellare are, that it captures “the properties that practical primitives really seem to possess.”

1. “Efficient” meaning polynomial-time in the size of its inputs. Also of course not every Turing reduction is polynomial time, but there’s only so much couching I can do before I lose everyone.

2. This is hard because the obvious definition of random is “given a bunch of input-output pairs, you are unable to tell anything about the output on any input you haven’t already seen”. In the context of a random oracle, this makes sense, because an oracle would be chosen at random at the beginning of the experiment. But for a hash function, if the hash function is publicly known, then the adversary can just make the queries itself. If we instead sample from a family of hash functions, that would eliminate that problem, but the ROM-secure schemes we’re talking about aren’t ones which randomly sample from a hash function family in every instantiation.

3. Section 4 in Canetti, Goldreich, Halevi

4. Section 2 in Holenstein, Maurer, Renner

5. As a reminder, a digital signature scheme consists of algorithms $\mathsf{KeyGen}$, $\mathsf{Sign}$, and $\mathsf{Ver}$. By “secure” I mean EUF-CMA-secure, meaning that an adversary can’t forge a valid signature for a message it’s never seen before. And by “quantum-secure” I mean the same thing but against a quantum-capable adversary.  2

6. This paper by Koblitz and Menezes presents good arguments for what the ROM has bought us and what avoiding the ROM has wreaked.

7. Canetti, Goldreich, Halevi generally argue that the ROM should be avoided for this reason.

8. I know that this notation is nonstandard, but I’m not using bra-ket notation because it’s not necessary for the rest of this piece.

9. This is section 3 in Boneh et al. The gist is there is an identification scheme that will either do the correct thing, or do the insecure thing if the adversary is able to compute some number of hash collisions in $O(\sqrt[3]{N})$ time. Since the best you can do in the classical case is find a collision with probability 1/2 in $O(\sqrt N)$ time, this is secure for all classical adversaries. But a quantum adversary running Grover’s algorithm can compute several collisions in $O(\sqrt[3]{N})$ time with high probability.

10. I left out the details here only because it’s very boring and takes up a bunch of space. If you want read the full proof, see section 3.2 in the aforementioned survey paper