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.

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).

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.² But the gist of the formalization is captured in the following definition:

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 given³ in 1998 by CGH, but I'd like to use a different example⁴ 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 scheme⁵ $\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:

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 cryptosystem⁶. 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?⁷ 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$.⁸ 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,

$$ F(\langle 010, 000 \rangle) = \langle 010, 111 \rangle \quad\textrm{and}\quad F(\langle 001, 000 \rangle) = \langle 001, 111 \rangle $$

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,

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

$$ \mathcal{O}_\mathrm{quant}\left( \frac{1}{\sqrt 3} \langle 010, 000 \rangle + \frac{i}{\sqrt 3} \langle 011, 000 \rangle - \frac{i}{\sqrt 3} \langle 110, 000 \rangle \right) = \frac{1}{\sqrt 3} \langle 010, \mathcal{O}(010) \rangle + \frac{i}{\sqrt 3} \langle 011, \mathcal{O}(011) \rangle - \frac{i}{\sqrt 3} \langle 110, \mathcal{O}(110) \rangle $$

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:

$$ \mathcal{O}_\mathrm{quant}(\langle x, 0 \rangle) = \langle x, \mathcal{O}(x)\rangle $$

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.⁹

§ 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.

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.¹⁰

§ Conclusions

And that's it! We've just constructed a signature scheme (assuming the existence of a quantum-secure⁵ 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."