In classical cryptography, the Random Oracle Model (ROM) is an invaluable tool for proving the security of protocols. It idealizes a cryptographic hash function as a completely random, publicly accessible black box. When a classical adversary wants to evaluate a hash, they must submit a specific input $x$ to receive a random output $y = H(x)$.
This step-by-step interaction allows a security proof's "simulator" to employ a technique called lazy sampling. The simulator does not need to determine the oracle's entire truth table in advance; instead, it generates random outputs on the fly, only when the adversary requests them. This gives the simulator the power to dynamically "program" the oracle—injecting cryptographic challenges into the oracle's responses to prove that breaking the protocol is as hard as solving a known difficult problem.
However, when the adversary is equipped with a quantum computer, this foundational proof technique collapses.
The Collapse of Classical Lazy Sampling
As formalized by Özgür Dagdelen et al. in Random Oracles in a Quantum World, a quantum adversary does not have to query a hash function one input at a time. Because hash functions are implemented locally via public code, an attacker can evaluate them in quantum superposition:
$$\sum_{x} \alpha_x |x\rangle |0\rangle \xrightarrow{H} \sum_{x} \alpha_x |x\rangle |H(x)\rangle$$
A single superposition query interacts with every possible entry in the oracle's truth table simultaneously. This capability introduces the Quantum-Accessible Random Oracle Model (QROM) and invalidates classical lazy sampling. If the simulator attempts to wait and see which input the adversary queries, it is already too late; the adversary has queried all of them. If the simulator tries to measure the incoming query to find out which inputs are being targeted, the measurement collapses the adversary's quantum state, ruining the simulation and invalidating the security proof.
As Mark Zhandry demonstrated in Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World, classical security definitions based on whether an adversary "queried a specific challenge message" become logically unsatisfiable in the QROM. Because a single superposition query touches every input, the adversary has technically queried the challenge message and every other message simultaneously, requiring entirely new proof methodologies.
Rebuilding Proofs with Compressed Oracles
To restore our ability to prove security against quantum adversaries, researchers had to reinvent how an oracle is simulated. The breakthrough came with the development of the compressed oracle framework.
Instead of treating the random oracle as a fixed classical function chosen at the start of the game, a compressed oracle models the database of the oracle itself as an evolving quantum state—a superposition of databases. Initially, the database state is an empty superposition, representing a function where no inputs have been decided.
When the adversary submits a query in superposition, the simulator does not collapse the query. Instead, it performs a quantum operation that entangles the adversary's query register with the database register. The database dynamically "records" information only for the inputs that have non-zero amplitudes in the adversary's query.
Classical ROM (Lazy Sampling):
Adversary: --- [ Query: x ] -----------> Simulator chooses random y
and records (x, y)
Quantum ROM (Compressed Oracle):
Adversary: --- [ Query: ∑ α_x |x⟩ ] ----> Simulator entangles query with
a superposition of databases,
tracking knowledge without collapse
This mechanism allows the simulator to track what the adversary "knows" without collapsing their quantum state. Jeremiah Blocki et al. utilized this technique in On the Security of Proofs of Sequential Work in a Post-Quantum World to prove that quantum attackers cannot bypass temporal constraints in blockchains, establishing formal bounds on the query complexity required to find sequential hash chains. Similarly, Ramis Movassagh et al. extended compressed oracle techniques to Haar random unitaries in Quantum Merkle Trees, allowing protocols to succinctly commit to large quantum states.
For digital signatures, simulators often leverage extractable quantum oracles. As shown by Carlos Aguilar-Melchor et al. in SDitH in the QROM, an extractable oracle allows a simulator to successfully extract a cryptographic witness or signature from the adversary's superposition queries, yielding tight security reductions that prevent the massive security parameter losses common when naively lifting classical proofs to the quantum domain.
Hardening Post-Quantum Primitives
The vulnerability of oracle-dependent protocols to quantum adversaries is not just a theoretical proof defect; it can lead to severe degradation in actual security margins.
For example, Boaz Barak et al. demonstrated in Merkle Puzzles are Optimal that key agreement protocols relying solely on a random oracle face a fundamental limit. While classical participants enjoy a quadratic security advantage over a classical attacker, quantum search algorithms like Grover's reduce this security margin to a linear relationship, making the protocol significantly easier to break.
To mitigate these vulnerabilities, a major line of research focuses on explicitly redesigning and verifying post-quantum primitives within the QROM:
- Digital Signatures: Many advanced signature schemes rely on the Fiat-Shamir transform to turn interactive identification protocols into non-interactive signatures. Researchers have systematically transitioned these constructions to the QROM to guarantee resistance against superposition queries, spanning symmetric-key signatures (Claudio Orlandi et al. in Digital Signatures from Symmetric-Key Primitives), lattice-based multi-signatures (Claudio Orlandi et al. in Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattices), code-based group signatures (Martianus Frederic Ezerman et al. in Provably Secure Group Signature Schemes from Code-Based Assumptions), and policy-based signatures (Yanhong Xu et al. in Traceable Policy-Based Signatures and Instantiation from Lattices).
- Key Exchange: Password-authenticated key exchange protocols have been hardened against quantum-capable attackers by shifting their underlying hardness assumptions to lattice problems like Ring Learning With Errors while proving security under superposition query models (Dongqing Xu et al. in Provably Secure Three-party Password Authenticated Key Exchange Protocol Based On Ring Learning With Error).
- Quantum Delegation and Protocols: The QROM is also used to secure purely quantum objectives. Jiayu Zhang leveraged the QROM in Delegating Quantum Computation in the Quantum Random Oracle Model to allow a weak classical client to securely delegate quantum tasks to a server, and later achieved verification of these computations in linear time (Classical Verification of Quantum Computations in Linear Time).
Unclonability and the Escape to the Plain Model
While the QROM provides a vital testing ground for security proofs, it remains an idealized abstraction. The ultimate goal of quantum cryptography is to achieve security in the plain model—relying on standard, concrete computational hardness assumptions rather than an imaginary random oracle. This transition is particularly crucial for unclonable cryptography, which uses the quantum no-cloning theorem to build software or data that cannot be duplicated.
Early foundational work by Scott Aaronson in Quantum Copy-Protection and Quantum Money established that quantum copy-protection is possible for unlearnable function families relative to a quantum oracle. This was expanded by Scott Aaronson et al. in New Approaches for Quantum Copy-Protection and Prabhanjan Vijendra Ananth et al. in Secure Software Leasing, demonstrating that software protection could be achieved by replacing complex quantum black boxes with classical oracle obfuscation techniques.
To eliminate the oracle entirely and move to the plain model, researchers developed a hybrid architecture that combines quantum states with classical indistinguishability obfuscation (iO).
The core mechanism relies on puncturable security. In this paradigm, a program's underlying cryptographic key can be "punctured" at a specific input, meaning the key can decrypt or evaluate every input except that one.
Plain Model Unclonable Architecture:
[ Quantum State ] ---> Enforces Unclonability (No-Cloning Theorem)
|
v (Linked mathematically)
[ Classical iO ] ---> Enforces Program Logic & Puncturable Security
As shown by Prabhanjan Vijendra Ananth et al. in A Modular Approach to Unclonable Cryptography, this architecture splits the security burden: a quantum token enforces unclonability via the no-cloning theorem, while a classical post-quantum obfuscated circuit handles the computation. By linking them mathematically, the authors proved that an adversary cannot split a single quantum decryption state into two functional pieces because doing so would require them to predict the output of the obfuscated circuit at a punctured point—violating standard computational assumptions like Learning With Errors.
By refining this link, Andrea Coladangelo et al. demonstrated in How to Use Quantum Indistinguishability Obfuscation that universal quantum copy-protection can be constructed from standard injective one-way functions. This framework demonstrates that the physical impossibility of cloning a quantum state can be successfully translated into a mathematical impossibility of bypassing classical cryptographic boundaries, eliminating the need for random oracles altogether.
Key Foundational Work
Merkle Puzzles are Optimal (2008) — contributed 3 concept elements to this direction.