PQC Research Series — Part 3

Quantum Random Oracle Model: Where Classical Proofs Stop Working

Author: Mayckon Giovani
Date: April 30, 2026
Series: PQC Research Series
Tags: PQC, Formal Methods, Cryptography, Systems

TL;DR

Security proofs built in ROM assume an oracle interface that quantum adversaries do not respect. In QROM the adversary can query the hash/KDF in superposition, which makes “record all queries,” “rewind,” and “program the oracle at $x^\star$” fundamentally different operations. Fiat–Shamir survives in many important cases, but the proof obligations are sharper, the reductions are typically less tight, and the system boundary (what is actually quantum-queryable) becomes part of the security statement. (1) (2) (3) (4)

Key takeaways

• QROM is a different oracle interface, not a stronger attacker in the same interface.
• In ROM, “lazy sampling + programming + rewinding” is a standard reduction toolbox; in QROM the same words denote operations that disturb the adversary state or require nontrivial bounds.
• Fiat–Shamir in QROM is possible but conditional: extraction is not generic, and tightness can degrade sharply.
• Systems matter: if your hash is public and deterministic, you should assume quantum-accessible evaluation (coherent implementation), even if the endpoints are classical.
• If your model boundary is wrong, your proof is irrelevant.

0. Context

ROM is “too useful” in practice: it turns hash functions into ideal objects and lets us prove security for transforms and protocols that are otherwise intractable. A large fraction of deployed cryptography (including most Fiat–Shamir-based signatures and many non-interactive ZK stacks) still leans on ROM-style reasoning.

The problem is that ROM assumes a classical interface to the oracle. In 2026 this is no longer the conservative model for any public, deterministic function (SHA-2/SHA-3/BLAKE2/BLAKE3, KDFs, transcript hashes): a quantum adversary can implement those circuits coherently and query them in superposition. That interface shift is exactly what QROM captures. (1)

Security proofs built in ROM assume an interface that quantum adversaries do not respect.

1. Problem Statement

Let $\lambda \in \N$ be the security parameter. Fix an output length $\ell(\lambda)$ and consider a random oracle $H$ as an idealized hash/KDF:

In classical ROM, an adversary $\adv$ is a PPT oracle machine that makes a sequence of classical queries $x_1,\dots,x_{q}$ and receives classical answers $H(x_i)$.

The security statement of a scheme $\Pi$ in ROM has the familiar shape:

Now change only one thing: the adversary is quantum polynomial-time and can query $H$ coherently in superposition. The right object is no longer a “function oracle” but a unitary oracle $U_H$.

The problem is then:

What changes when the adversary can query the oracle in superposition?

Formally, we want to understand how the advantage bound, the reduction technique, and the proof obligations change when we move from ROM to QROM:

The answer is not “add Grover factors.” The answer is: the proof techniques themselves stop being valid unless reworked. (1) (2)

2. Formal Model

2.1 Classical ROM — Formal Definition

2.1.1 Oracle definition and interaction

In ROM, the challenger samples a function $H$ uniformly from the set of all functions $\{0,1\}^\ast \to \{0,1\}^{\ell(\lambda)}$. The adversary interacts via classical queries:

The standard implementation of ROM in proofs is lazy sampling: $H(x)$ is defined on first query and stored in a table.

state T : map from {0,1}* to {0,1}^ℓ

Oracle H(x):
  if x ∈ dom(T): return T[x]
  y ←$ {0,1}^ℓ
  T[x] := y
  return y

This is the object that enables classical ROM proof moves.

2.1.2 Classical proof moves in ROM

ROM reductions frequently rely on three operations:

1. Observe queries. The reduction records every $x$ queried to $H$.
2. Reprogram the oracle. The reduction sets $H(x^\star) := y^\star$ after seeing some adversary behavior.
3. Rewind. The reduction replays the adversary from a previous point with modified oracle responses to extract a witness (forking lemma style).

These moves are not “syntactic conveniences.” They are model-level assumptions about the oracle interface.

2.2 QROM — Formal Shift (where the pain starts)

2.2.1 Unitary oracle interface

In QROM, the oracle is a unitary operation over two registers:

A QROM adversary $\adv_Q$ is a QPT algorithm (poly-size uniform quantum circuits) that can interleave its own unitaries with calls to $U_H$:

The observable object is not a query transcript. It is a final classical measurement outcome after a sequence of coherent operations.

One subtlety that matters for proofs: in ROM, “lazy sampling” gives a concrete simulation strategy for $H$ without ever materializing the full random function. In QROM, you still conceptually sample a random function $H$, but the adversary’s access is through a unitary $U_H$ that must behave consistently on superpositions. Naively “defining $H(x)$ on demand” is no longer a complete description of how the oracle acts, because the simulator cannot simply observe which $x$ values are being queried.

This is the gap that QROM techniques bridge: they construct simulators and hybrid arguments that bound what a $q$-query quantum adversary can learn or distinguish about changes to $H$ without requiring an impossible transcript log. (1) (2)

2.2.2 Why “recording queries” is not a primitive

Consider a single query state in the $x$-register:

After the oracle call:

The query register is now entangled with the answer register. If the reduction measures the query register to “see which $x$ was asked,” it collapses the state and changes the adversary’s future behavior. There is no free transcript.

You can make this quantitative with the right notion of “disturbance.”

Let $x^\star$ be a point you care about (e.g., the fork point, the programmed point). Define the projector $P = |x^\star\rangle\langle x^\star|$ on the query register and let:

If you measure the two-outcome POVM $\{P, I-P\}$ and discard the outcome, you obtain a mixed state $\rho$. The trace distance to the original state is bounded by a term on the order of $\sqrt{p}$ (formal constants depend on the exact measurement map, but the scaling is the key): if the adversary assigns negligible amplitude to $x^\star$, then “checking whether $x^\star$ was queried” can be a gentle operation; if it assigns non-negligible amplitude, measurement meaningfully perturbs the computation. (For the standard trace-distance/fidelity calculus underlying these bounds, see e.g. Nielsen–Chuang and the Fuchs–van de Graaf inequalities.) (5) (6)

That is the deep point: in QROM, “did it query $x^\star$?” is not a boolean event. It is an amplitude question.

This is why ROM techniques need replacement lemmas (compressed oracle, measure-and-reprogram, quantum rewinding variants) instead of direct reuse. (2) (7)

flowchart LR
  A["ROM reduction"] --> T["classical transcript"]
  A --> P["point programming at x_star"]
  A --> R["rewinding / forking"]
  Q["QROM adversary state (ket psi)"] --> X["measurement disturbance"]
  X --> T
  X --> R
  Q --> UH["unitary oracle U_H"]

2.3 Where Classical Proof Techniques Break

2.3.1 Rewinding fails (in general)

Classical rewinding assumes you can replay $\adv$ from a previous internal state. Quantum algorithms do not expose their internal state without measurement, and measurement is destructive.

More formally, let the adversary’s internal state at some point be $|\psi\rangle$. Any attempt to “copy” $|\psi\rangle$ violates no-cloning, and any attempt to “observe” it induces a measurement map $\mathcal{M}$ that changes the state.

There are quantum rewinding techniques (Watrous-style) that work for restricted protocol structures (public-coin, certain ZK settings), but they are not a generic replacement for the classical forking lemma pipeline used in ROM proofs. In other words: the extraction interface changes. (7)

2.3.2 Programming the oracle is a global operation

In ROM, reprogramming is local: define $H(x^\star)$ late, or change it, and reason about the probability that $\adv$ queried $x^\star$.

In QROM, reprogramming is not local in the same way because the adversary can query $x^\star$ with small amplitude across many coherent queries.

A standard quantitative intuition is captured by “hybrid” bounds for quantum queries: if two oracles $H$ and $H'$ differ on a small set of inputs, then any $q$-query QPT distinguisher has advantage bounded by a term that scales like $q\sqrt{t/|D|}$ (domain size $|D|$, difference set size $t$). In the single-point case ($t=1$), the effect of changing one value is upper bounded by $\tilde{O}(q/\sqrt{|D|})$. This is the same phenomenon behind Grover optimality bounds. (8)

To make that concrete, fix a finite domain $D$ with $|D|=N$ and consider two random oracles $H,H'$ that are identical everywhere except at a single point $x^\star$ where $H(x^\star)\neq H'(x^\star)$. Then any quantum algorithm $\adv_Q$ making at most $q$ quantum queries to the oracle satisfies an inequality of the form:

up to constant factors (and with extensions to $t$-point differences). This is exactly why point programming needs amplitude accounting in QROM rather than transcript accounting in ROM. (8)

The same bound is a useful engineering sanity check: it shows when “reprogramming one point” is statistically invisible versus when it is potentially detectable.

xychart-beta
    title "Single-point oracle difference bound (toy scaling)"
    x-axis ["0","40","80","120","160","200","240","280","320","360","400","440","480","520","560","600","640","680","720","760","800"]
    y-axis "O(q/√N)" 0 --> 1
    line "N = 2^20" [0.0,0.039063,0.078125,0.117188,0.15625,0.195313,0.234375,0.273438,0.3125,0.351563,0.390625,0.429688,0.46875,0.507813,0.546875,0.585938,0.625,0.664063,0.703125,0.742188,0.78125]
    line "N = 2^40" [0.0,0.000038,0.000076,0.000114,0.000153,0.000191,0.000229,0.000267,0.000305,0.000343,0.000381,0.000420,0.000458,0.000496,0.000534,0.000572,0.000610,0.000648,0.000687,0.000725,0.000763]

This bound is both good news and bad news:

• good: small reprogrammings can be statistically invisible up to a regime,
• bad: you cannot justify “it didn’t query $x^\star$” by reading a transcript, because there is no transcript.

Zhandry’s “compressed oracle” technique is one of the key tools that makes these arguments precise: instead of logging queries, you reason about the adversary’s interaction with an evolving classical description of a quantum-accessed oracle. (2)

2.3.3 Fiat–Shamir starts to crack

Fiat–Shamir (FS) takes an interactive proof/identification protocol and replaces the verifier’s random challenge with a hash of the transcript. In ROM this is natural: a random oracle is a model of “perfect challenge generation.”

In QROM, the adversary can query the oracle in superposition before committing to a transcript, and it can maintain quantum state that is entangled with oracle answers. This breaks the standard ROM proof skeleton:

• the extractor cannot reliably fork by rewinding,
• programming $H$ at one point is not a benign point change without extra reasoning,
• and “the adversary must have queried $H$ at the forgery point” is no longer a classical event you can check by inspecting a log.

The result is not that FS is “broken.” The result is: classical FS proofs do not lift automatically. You need QROM-aware arguments and, often, additional conditions on the underlying protocol (special soundness, commitment structure, etc.). (3) (4)

2.4 Deep Dive — Fiat–Shamir in a Quantum World

2.4.1 $\Sigma$-protocol model

Consider a (public-coin) $\Sigma$-protocol for relation $\mathcal{R} \subseteq \mathcal{X}\times\mathcal{W}$ where $x\in\mathcal{X}$ is a statement and $w\in\mathcal{W}$ is a witness.

The interactive protocol is:

1. Prover samples randomness $\rho$ and sends commitment $a \leftarrow \textsf{Commit}(x,w;\rho)$.
2. Verifier samples challenge $c \leftarrow \{0,1\}^k$ and sends $c$.
3. Prover sends response $z \leftarrow \textsf{Respond}(x,w;\rho,c)$.
4. Verifier checks $\textsf{Verify}(x,a,c,z)=1$.

Special soundness (the typical extraction property) says:

2.4.2 Fiat–Shamir transform

FS removes the verifier by setting:

for message $m$ (for signatures) or context string. The prover outputs $(a,z)$ and the verifier recomputes $c$ from $H$.

In ROM, a standard security proof sketch for FS-based signatures is:

1. assume a forger outputs a valid transcript $(a,z)$ for $c=H(\cdot)$,
2. by forking (rewinding with different oracle programming) obtain two transcripts with same $a$ and different $c$,
3. apply special soundness to extract $w$.

This pipeline depends on an extractor that can:

• observe whether/when the forger queried $H$ at $(x,a,m)$,
• program $H$ at that point to force a different $c'$,
• rewind the forger to re-run with the modified oracle.

2.4.2.1 A QROM-flavored EUF-CMA game (what you are actually claiming)

To avoid hand-waving, write the security claim in a game form that matches deployment reality.

An FS-based signature scheme $\Sigma_{\textsf{FS}}$ (built from a $\Sigma$-protocol) is typically verified under EUF-CMA:

• $\textsf{KeyGen}(1^\lambda)$ outputs $(\mathsf{pk},\mathsf{sk})$ where $\mathsf{pk}$ is the statement and $\mathsf{sk}$ is the witness.
• $\textsf{Sign}(\mathsf{sk},m)$ runs the prover to produce $(a,z)$ with challenge $c := H(\mathsf{pk},a,m)$ and outputs $\sigma := (a,z)$.
• $\textsf{Verify}(\mathsf{pk},m,\sigma)$ recomputes $c := H(\mathsf{pk},a,m)$ and checks $\textsf{Verify}_\Sigma(\mathsf{pk},a,c,z)=1$.

The QROM security game then looks like:

1. Challenger samples $(\mathsf{pk},\mathsf{sk})$ and a random oracle $H$.
2. $\adv_Q$ is a QPT adversary with quantum oracle access to $U_H$ and classical access to a signing oracle $\textsf{Sign}(\mathsf{sk},\cdot)$.
3. $\adv_Q$ outputs $(m^\star,\sigma^\star)$.
4. $\adv_Q$ wins iff $\textsf{Verify}(\mathsf{pk},m^\star,\sigma^\star)=1$ and $m^\star$ was not previously signed.

Define advantage:

The key detail is the mixed interface: the adversary has quantum access to $H$ (because $H$ is public and coherently computable) but only classical access to the signer (because signing is an external system interface). This mixed typing is not a nuance — it is what makes many reductions either possible or impossible. (1) (3)

2.4.3 Why the extractor is not generic in QROM

In QROM, the forger can query $H$ in superposition on many candidate $(x,a,m)$ values, potentially entangled with its internal randomness and commitments.

There is a core impossibility shape here: for general FS instantiations, black-box extractors of the classical type do not exist in QROM without additional structure. The reason is precisely that “the fork point” is not a classical observable event. Extraction requires different techniques (quantum rewinding variants, measure-and-reprogram, compressed oracle arguments) and tends to be protocol-specific. (3) (4)

2.4.4 A concrete quantitative lens: Grover-style query economics

Even before extraction, QROM changes the economics of oracle access. Many ROM security arguments implicitly assume a classical $q$-query adversary cannot do much better than $q/|D|$ for preimage-style events. In QROM, unstructured search admits quadratic speedup with $O(\sqrt{|D|})$ queries (Grover), and this is optimal (BBBV). (9) (8)

This does not “break” FS by itself, but it changes the bound calculations that sit under heuristic security-level claims.

Below is a simulation of success probability for preimage search on a domain of size $N=2^{20}$, comparing a classical $q$-query strategy ($p \approx q/N$) versus ideal Grover amplitude amplification ($p=\sin^2((2q+1)\arcsin(1/\sqrt{N}))$).

xychart-beta
    title "Preimage search success probability (N = 2^20)"
    x-axis ["0","40","80","120","160","200","240","280","320","360","400","440","480","520","560","600","640","680","720","760","800"]
    y-axis "Pr[success]" 0 --> 1
    line "Classical q/N" [0.0,0.000038,0.000076,0.000114,0.000153,0.000191,0.000229,0.000267,0.000305,0.000343,0.000381,0.000420,0.000458,0.000496,0.000534,0.000572,0.000610,0.000648,0.000687,0.000725,0.000763]
    line "Grover" [0.0,0.003055,0.012204,0.027373,0.048452,0.075300,0.107744,0.145579,0.188571,0.236456,0.288945,0.345723,0.406451,0.470767,0.538291,0.608624,0.681356,0.756065,0.832321,0.909688,0.987729]

Two notes for engineers reading this:

1. This is a toy curve about oracle-query economics. It is not a complete security argument for any specific scheme.
2. It is exactly the kind of difference that turns “ROM intuition” into “QROM accounting.” If the proof’s hidden constant is “adversary must query $H$ at $x^\star$,” you need to reason about quantum query amplitude, not classical query events.

2.5 Attempts to Fix the Problem (what actually works)

The literature does not stop at criticism. There is a well-developed toolchain for QROM reasoning, but it is heavier and more conditional than ROM reasoning.

2.5.1 Compressed oracle and query recording

Zhandry’s compressed oracle framework gives a way to reason about quantum queries by representing the oracle state as a compressed classical structure plus a bound on how much information a $q$-query adversary can extract. This underpins a number of indifferentiability and reprogramming arguments in QROM. (2)

2.5.2 QROM Fiat–Shamir proofs (Unruh; Don–Fehr–Majenz–Schaffner)

Unruh established QROM security of Fiat–Shamir under conditions that essentially replace the classical forking lemma with a quantum-aware argument (often called a “quantum forking lemma” in informal discussion). (3)

Don et al. refine and systematize the analysis of FS in QROM, providing proofs (and clarifying limitations) for broad classes of $\Sigma$-protocols and related transforms. (4)

2.5.3 Quantum rewinding (Watrous)

Watrous showed that certain zero-knowledge proofs remain secure against quantum adversaries using specialized quantum rewinding. This is not a generic drop-in for classical rewinding, but it demonstrates that the right structure can make extraction/simulation possible. (7)

3. System Constraints

Systems, not just proofs

The cryptographic statement “QROM adversary can query $H$ in superposition” is often misunderstood as a claim about the endpoints being quantum.

It is not. Endpoints can remain classical.

QROM is a claim about the adversary’s ability to implement the oracle coherently given a public description. Hash functions are public, deterministic circuits. If an attacker has a quantum computer, it can run $H$ as a quantum circuit and query it on a superposition. That is true regardless of whether your server is classical, embedded, or IIoT.

This is why QROM is not optional for long-lived infrastructure. If your security boundary assumes “the attacker cannot evaluate $H$ coherently,” you need to justify that assumption at the system level (rate-limited remote oracles, hardware-enforced classical interfaces, etc.). Otherwise you are not in ROM; you are in QROM by default.

3.1 System constraints that proofs ignore

Formal QROM proofs also assume an idealized interface on the defender side:

• unbiased randomness for keygen and masking,
• constant-time behavior where required,
• memory erasure where ephemerality is assumed,
• and no side-channel observation beyond what the model states.

In PQC implementations, the gap between proof model and deployed system can be larger than in classical ECC/RSA code because state and bandwidth are larger and performance pressure is higher.

4. Core Argument / Insight

QROM does not just make attacks stronger. It invalidates the assumptions behind how we prove security.

If your proof relies on:

• query observability,
• transcript extraction,
• point programming without global entanglement analysis,
• classical rewinding / forking,

then your ROM proof is not evidence of security against quantum-capable adversaries. You need an explicit QROM argument, or you need to explicitly justify that your system boundary makes only classical oracle access relevant.

5. Implications

5.1 PQ signatures: ROM proofs are not the end of the story

Many modern signature schemes (including lattice-based families) are structurally tied to FS-style transforms. Even when standards documents present security arguments, the long-term claim you care about is a QROM claim, not a ROM claim.

This is not panic. It is model hygiene:

A proof in ROM is not evidence of security in a quantum-capable world.

5.2 ZK and blockchain: the Fiat–Shamir heuristic is infrastructure

Most deployed ZK proof systems in blockchains are non-interactive by applying Fiat–Shamir to interactive protocols. If your security story assumes ROM and you deploy into a 10–20 year horizon where quantum adversaries are plausible, you need to understand which parts of your system are actually proven in QROM and which are heuristic.

5.3 Protocol design: treat the oracle interface as a first-class spec object

At the protocol level, the correct engineering move is to define the oracle model explicitly:

• what functions are modeled as random oracles (hash/KDF/transcript),
• what the adversary interface is (classical evaluation vs coherent evaluation),
• what the resource budgets are (query bounds, time, memory, coherence),
• what the system boundary prevents (if anything).

Without that, “post-quantum” becomes a label rather than a claim.

Failure modes

• Treating QROM as “ROM + Grover factor” and carrying ROM proofs forward unchanged.
• Assuming rewinding-based extractors still work because “we can just rerun the adversary.”
• Treating oracle programming as a harmless point change without a QROM reprogramming bound.
• Confusing “adversary is quantum” with “endpoints are quantum,” and therefore under-modeling oracle access.

What to monitor

• Where your stack uses Fiat–Shamir (signatures, transcripts, ZK proofs, aggregations).
• Which proofs are explicitly QROM (and what the tightness/assumptions are) versus “ROM only.”
• Whether the system boundary truly enforces classical oracle access (it usually does not for hash functions).
• Implementation regressions that invalidate model assumptions (randomness bias, timing leakage, memory non-erasure).

Rollback plan

If you deploy primitives/protocols whose story changes materially between ROM and QROM, treat that as an agility requirement:

• version suite IDs explicitly (no aliasing of “equivalent” constructions),
• bind suite choice into transcript authentication,
• keep a deprecation window and telemetry for legacy behavior,
• and pre-plan re-keying / credential rollover paths.

6. Continuity Hook

Part 4 will be about tightness and parameter inflation: how QROM-aware proofs often introduce additional loss factors, how those losses map (or fail to map) into concrete parameter sizing, and why “Category 5” language can hide fragile reductions.

7. References

Evidence

• The formal distinction between ROM and QROM and the oracle interface shift is made explicit in Boneh et al. (1)
• Concrete QROM techniques (recording queries / compressed oracle) are developed by Zhandry. (2)
• The limits and conditions of Fiat–Shamir in QROM are analyzed by Unruh and by Don et al. (3) (4)
• Grover/BBBV quantify the structural query-economics shift that sits underneath many ROM intuitions. (9) (8)
• Watrous gives a canonical example of when quantum rewinding works and when it does not generalize. (7)

Checklist

• For every security claim, state whether it is ROM, QROM, or “quantum computation with classical oracle access.”
• For every FS usage, identify the extraction/simulation proof technique (and whether it is QROM-valid).
• Document query/time/memory/coherence budgets as part of the security target.
• Track proof tightness losses and map them into concrete parameter sizing.
• Treat parameter inflation as a side-channel and ops-risk amplifier.

Further reading

• Boneh et al., “Random Oracles in a Quantum World” (ePrint 2010/428). (1)
• Zhandry, “How to Record Quantum Queries…” (ePrint 2018/276). (2)
• Unruh, “Post-Quantum Security of Fiat-Shamir” (ePrint 2017/398). (3)
• Don–Fehr–Majenz–Schaffner, “Security of the Fiat-Shamir Transformation in the QROM” (ePrint 2019/190). (4)
• Watrous, “Zero-Knowledge Against Quantum Attacks” (SIAM J. Comput., 2009). (7)
• Grover, “A fast quantum mechanical algorithm for database search” (1996). (9)
• BBBV, “Strengths and Weaknesses of Quantum Computing” (1997). (8)