I'm reading this paper on quantum random oracles, and I have some fundamental questions about certain statements that seem to be intuitive (but I can't seem to figure it out). My goal is to have a deeper understanding of the QFT and it's uses.

My question has to do with an example from the paper. Here, $h_0:\{0,1\}^{2n}\to\{0,1\}^n$ is just some compression function.

(page 4)[The adversary] sets up the uniform superposition $\sum_{x,y}|x,u\rangle$ and queries. In the case where $h_0$ Is a classical function, then this state becomes $$\sum_{x,u}|x,u\oplus h_0(x)\rangle=\sum_{x,u}|x,u\rangle.$$ Namely, the state is unaffected by making the query. In contrast, the simulated query would result in $$\sum_{x,u}|x,u\oplus y\rangle\otimes|x,y\rangle.$$ Here, the adversary's state is now entangled with the simulator's. It is straightforward to detect this entanglement by applying the QFT to the adversary's $x$ registers, and then measuring the result.

What does it mean for the quantum adversary to query a classical function? Why does it have no effect? Next, why is it easy to see that you can check for entanglement using the QFT on the $x$ registers? My understanding is that applying the QFT would just give you some kind of frequency information, so if the $x$ registers were in the uniform superposition I'd think you'd always get $|0\rangle$

  • $\begingroup$ Hi and welcome to Quantum Computing SE! I've edited your post so that it contains a single question. Please feel free to write another post to get an answer to your second question! $\endgroup$
    – Tristan Nemoz
    Commented Apr 10, 2022 at 22:37

1 Answer 1


To answer your question, it is required to give a bit of context on this paper.

In cryptography, the random oracle is a technique in which you assume that when the adversary queries the oracle for $h(x)$, two cases could happen:

  1. The adversary never asked the oracle the value of $h(x)$ before. In this case, the oracle picks a random value $y$, sets $h(x)=y$ and returns $y$ to the adversary.
  2. The adversary already asked the oracle the value of $h(x)$, in which case the oracle returns the value it returned the first time.

This technique has been used in numerous proofs, and a quantum equivalent is desired to make some security proofs work. Note that in this case, it is completely equivalent to work with a random function $h$.

However, something inherently classical is part of the definition of a random oracle: the oracle must know whether the adversary already queried $h(x)$ once to return the value. But when the query is a superposition one, what is the oracle supposed to do? The adversary must not know that the oracle records their queries. In fact, the adversary must not be able to differentiate between interacting with the quantum random oracle and interacting with an oracle implementing a random function.

The example that your question is about describes a naive strategy for the oracle, and shows that such a strategy doesn't work, as the adversary can know whether they interact with a random oracle applying this strategy or with an oracle implementing a random function.

Let $h_0$ be our random classical function. Let $\mathcal{O}$ be the quantum random oracle and let $\mathcal{O}_{h_0}$ be the oracle implementing $h_0$. In this strategy, $\mathcal{O}$ applies a C-NOT between the adversary's query and a local register before choosing a random value $y$: $$\sum_{x,u}\alpha_{x,u}|x,u\rangle\to\sum_{x,u}\alpha_{x,u}|x,u\oplus y\rangle_{\text{A}}|x,y\rangle_{\text{O}}$$ I've denoted with a subscript $\text{A}$ the registers returned to the adversary and with $\text{O}$ the ones the oracle keeps. The intuition is that when the adversary measures their registers, they will get a random value $y$ associated to the measure of the register containing $x$. Since this also collapsed the oracle's database, the oracle knows that $h(x)=y$ from now on and can act accordingly.

As a recall, when the adversary interacts with $\mathcal{O}_{h_0}$, the following happens: $$\sum_{x,u}\alpha_{x,u}|x,u\rangle\to\sum_{x,u}\alpha_{x,u}\left|x,u\oplus h_0(x)\right\rangle$$ Now, what happens if the adversary's query is the uniform superposition? If the adversary interacts with $\mathcal{O}_{h_0}$, then the state of the system is: $$\sum_{x,u}\left|x,u\oplus h_0(x)\right\rangle$$ You can convince yourself that this state is exactly the uniform superposition. Indeed, that's more easily seen when writing this state as: $$|0\rangle\sum_u\left|u\oplus h_0(0)\right\rangle+|1\rangle\sum_u\left|u\oplus h_0(1)\right\rangle+\cdots$$ For each $i$, $h_0(i)$ is a random but fixed bitstring. As such, $\sum_u\left|u\oplus h_0(i)\right\rangle$ contains exactly each basis state once, since the function $x\mapsto x\oplus h_0(i)$ is bijective. The state can thus be written as: $$|0\rangle\sum_u\left|u\right\rangle+|1\rangle\sum_u\left|u\right\rangle+\cdots=\sum_{x}|x\rangle\sum_u|u\rangle=\sum_{x,u}|x,u\rangle$$ Hence, if the adversary applies a QFT gate on this system and measure it, it will result in state $|0,0\rangle$ with probability $1$.

However, if the adversary interacts with the quantum random oracle, the state of the system is: $$\sum_{x,u}|x,u\oplus y\rangle_{\text{A}}|x,y\rangle_{\text{O}}$$ In this case, the adversary's registers are entangled with the oracle's. If the adversary applies a QFT gate on these registers and measure them, it will result in state $|0,0\rangle$ with negligible probability ($\frac{1}{2^{n}}$ if I'm not mistaken, with $n$ being the size of the adversary's $x$ register).

Thus, this strategy cannot be used to simulate a quantum random oracle, since an adversary is able to distinguish between this quantum random oracle and an oracle implementing a classical random function. The whole point of Zhandry's paper is to describe a technique that the quantum random oracle can apply to be indistinguishable from an oracle implementing a random function.

  • $\begingroup$ Thanks so much for your detailed response! I have some follow-up questions First, I'm a bit confused about the quantum random oracle. I would think the oracle maps $\sum_{x,u}|x,u\rangle\to\sum_{x,u}|x,u\oplus y_x\rangle$, where each $y_x$ is chosen uniformly at random. I don't understand why on one hand we say $$\sum_{x,u}\alpha_{x,u}|x,u\rangle\to\sum_{x,u}\alpha_{x,u}|x,u\rangle_{\text{A}}|x,u\oplus y\rangle_{\text{O}}$$ and then later state $$\sum_{x,u}|x,u\oplus y\rangle_{\text{A}}|x,u\rangle_{\text{O}}.$$ Aren't these different results from the same process of querying $\mathcal O$? $\endgroup$ Commented Apr 12, 2022 at 4:47
  • $\begingroup$ Second, why should $\sum_{x,u}|x,u\oplus h_0(x)\rangle$ be the uniform superposition? If the adversary is querying on $\sum_{x,u}|x,u\rangle$ and $h_0$ is a function chosen uniformly at random, then, for example, it could be the case that for each $x\in\{0,1\}^{2n}$, $h_0(x)=u$ (what the adversary has in the range registers). Then I would think the result would be $\sum_{x,u}|x,0\rangle$, which isn't the uniform superposition. In which places am I misunderstanding? Thanks again $\endgroup$ Commented Apr 12, 2022 at 4:56
  • $\begingroup$ @FlamtapShuckle For the first part of your first question, that would be equivalent to choosing a fixed function rather than choosing random values on the fly. Zhandry describes the problems that comes with this approach on the last two paragraphes on page 4 of the paper. For the second part of your first question, there was a typo in my answer, thanks for having spotted it! Finally, I've edited my post to answer why this state is actually the uniform superposition. What you've missed is that $h_0(x)$ is fixed for each $x$, thus it cannot be equal to $u$, since $u$ is itself in superposition. $\endgroup$
    – Tristan Nemoz
    Commented Apr 12, 2022 at 7:57
  • $\begingroup$ Thanks again. Despite reading and writing it, I totally was thinking of the $|u\rangle$ registers as fixed. Now it makes sense why the state would be unchanged in the first case. In the simulated case, we're saying that when the adversary queries in the uniform superposition $\sum_{x,u}|x,u\rangle$ then the simulator chooses a single $y$ to apply to all possible $|x,u\rangle$?. This would mean the resulting state is $$|0\rangle\sum_u|u\oplus y\rangle + |1\rangle\sum_u|u\oplus y\rangle+\dots$$ I don't see how this simulated oracle is actually answering the superposition of queries $\endgroup$ Commented Apr 12, 2022 at 20:29
  • 1
    $\begingroup$ @FlamtapShuckle Zhandry's compressed oracle (the one thata ctually works, not the one we were talking about) does not choose a single value $y$ in reality: it prepares some state in an uniform superposition and then wait for the adversary to measure its registers, which is the only way they can learn $h(x)=y$. When they do so, the oracle's database collapses simultaneously and the oracle now has a database containing the value the adversary learned upon measuring their registers. Does that make sense to you? $\endgroup$
    – Tristan Nemoz
    Commented Apr 13, 2022 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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