Quantum Random Oracle Model

Short answer: Many cryptographic proofs treat a hash function as a "random oracle" that an attacker can only query with ordinary inputs. A quantum attacker could query it with a superposition of inputs, so proofs for post-quantum schemes need the quantum random oracle model (QROM). Research papers show the two models genuinely differ, and give conditions and techniques under which classical proofs carry over. This is proof methodology, not a statement about any particular product.

Why the classical model is not enough

A paper first circulated in 2010 and presented at Asiacrypt 2011 starts from the observation that post-quantum cryptography means classical systems that stay secure against a quantum adversary. Some proposed systems are set in the random oracle model and proven secure against adversaries with only classical access to the oracle. The authors argue that to prove post-quantum security, one needs to prove security in the quantum-accessible random oracle model, where the adversary can query the oracle with a quantum state.

They support this by separating the models. They present a scheme that is secure when the adversary has classical access to the random oracle but insecure when the adversary can make quantum oracle queries. A later paper explains the difficulty: a quantum adversary can make a single query on a superposition of inputs and receive a superposition of outputs, and by the basic properties of quantum mechanics one cannot simply observe such a query the way classical proofs do, which obstructs the usual advantages of the classical model.

When classical proofs carry over

The 2010 paper then develops generic conditions under which a classical random-oracle proof implies security in the quantum model. It introduces history-free reductions, a category of classical reductions that determine oracle answers independently of the history of previous queries, and proves that such reductions imply quantum-model security. It shows that certain post-quantum proposals, including ones based on lattices, can be proven secure this way, and ends with a rich set of open problems.

Fiat-Shamir in the quantum model

A 2019 paper studies the Fiat-Shamir transformation, which turns a three-round public-coin interactive proof into a non-interactive proof in the random-oracle model, against a quantum adversary that can query the oracle in superposition. Its main result is a generic reduction: any quantum dishonest prover attacking the transformed proof in the QROM can be turned into a similarly successful quantum prover attacking the underlying interactive protocol in the standard model. As a result, soundness and proof-of-knowledge properties in both their computational and statistical forms are preserved under the transformation even with quantum attacks. The authors say this improves and completes earlier partial results and proves wrong certain claims in the literature. For signatures, it implies that for protocols that are proofs of knowledge against quantum provers, with some additional natural properties, the Fiat-Shamir signature scheme is secure in the QROM. As an example they conclude that the non-optimized Fish scheme, the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.

What this does not tell you

A proof in the QROM is relative to an idealised hash function, and real hash functions are not random oracles. These papers do not assess any deployed system, and the conclusions apply to the constructions and conditions they state.

FAQ

What is a random oracle?

An idealised hash function the adversary can only query, used in security proofs.

Why a quantum version?

A quantum adversary could query the oracle with a superposition of inputs, which the classical model does not allow.

Do classical proofs still apply?

Sometimes. The 2010 paper shows history-free reductions carry over, and the 2019 paper does this for Fiat-Shamir.

Is the difference real?

Yes. The 2010 paper presents a scheme secure with classical oracle access but insecure with quantum queries.

Does a QROM proof mean a product is secure?

No. It is a proof about a construction under idealised assumptions.