Are one-way functions still minimal against quantum adversaries?

Classically every useful primitive implies them. The classical proof rewinds, and rewinding destroys a quantum adversary’s state.

Motivation

One-way functions are the minimal assumption of classical cryptography: identification, symmetric encryption, commitments and coin flipping all imply them, and the implications are proved by black-box reductions that use the primitive and the adversary as oracles.

Post-quantum cryptography keeps the protocols and challengers classical and makes only the adversary quantum. That sounds like a small change, and for the primitives themselves it often is — but the proof that they imply one-way functions may not survive it. A classical security reduction is free to rewind its adversary, and rewinding a quantum adversary destroys the state it was in. So the classical hierarchy does not automatically transfer, and whether it transfers at all is the question this hub tracks.

It is worth being clear about what is not being asked. Fully quantum cryptography appears to have a different hierarchy entirely — there are oracles relative to which pseudorandom quantum states exist while \(\mathbf{BQP} = \mathbf{QMA}\) — so quantum primitives may not sit above one-way functions in the first place. The post-quantum regime is the intermediate one, and the one where the classical answer might still hold.

Provenance and history

One source paper: Buxbaum and Mahmoody, A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography, ePrint 2024/2095; published in IACR Communications in Cryptology, 2024. Verified against ePrint on 18 August 2026 — this is the one draft in the harvest whose bibliographic details the harvester read off the page rather than inferring.

The statement was drafted by scripts/harvest_conjectures.py from that PDF and is AI-written and unreviewed, as its status badge says.

Parameter lattice

The axis that matters is how the classical implication from the primitive to one-way functions was established.

classical security implication witnessed by adversary class status
a black-box reduction between the security games uniform quantum (\(\mathsf{QPT}\)) settled — Theorem 1
the same non-uniform quantum settled — Theorem 2
the same, assuming a deterministic adversary either settled — Theorem 3
anything else — a reduction using the adversary’s code either open — c/0029

The paper’s results all carry the black-box hypothesis inside the theorem statement, and the open statement is the corollary with exactly that hypothesis deleted. The paper takes no position on which way it goes, which is worth repeating: this is an open question, not a conjecture the authors expect to be true.

Statements in this hub