Post-Quantum Minimality of One-Way Functions Under Non-Black-Box Security Reductions

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Classically, one-way functions are minimal: essentially every primitive worth having implies them. Post-quantum cryptography keeps everything classical except the adversary, and the classical proofs of minimality do not obviously survive that, because they may rewind an adversary whose state cannot be rewound. The source paper shows minimality does transfer whenever the classical implication is witnessed by a black-box reduction between the security games. What is left open — and this statement — is whether it transfers when the classical proof used the adversary’s code.

View PDF · Download LaTeX source

Fix a class of efficient quantum adversaries \(\mathcal{E} \in \{\mathsf{QPT}, \mathsf{QPT}/\mathrm{poly}\}\) and keep it fixed. Let \(\mathcal{Q} = (F_{\mathcal{Q}}, R_{\mathcal{Q}})\) be any classical primitive with a game-based security definition, with challenger \(C_{\mathcal{Q},f}\) and success threshold \(t_{\mathcal{Q}}\), and let \(\mathcal{F}\) be the one-way function primitive.

Suppose a potentially non-constructive reduction from \(\mathcal{F}\) to \(\mathcal{Q}\) exists in the paper’s sense — the formalization of “classically, the existence of \(\mathcal{Q}\) implies the existence of one-way functions”. No assumption is made about how its security clause is established: the passage from a PPT adversary breaking \(g_f\) to a PPT adversary breaking \(f\) need not be witnessed by a black-box reduction between the two games, and may depend arbitrarily on the code of the adversary.

Conjecture. If the post-quantum variant \(\mathcal{Q}'\) of \(\mathcal{Q}\) against \(\mathcal{E}\) exists, then one-way functions secure against \(\mathcal{E}\) exist — that is, the post-quantum variant \(\mathcal{F}'\) of \(\mathcal{F}\) exists.

The definitions carry one input that is easy to drop and is load-bearing: the reduction is given \(1^{1/\varepsilon}\) as a parameter, which the source’s Definition 5 and its footnote require and which its proof calls crucial. Dropping it would inflate the region the settled results already cover.

Open exactly in the non-black-box case, and the settled region is delimited by hypotheses that appear inside the theorems rather than in surrounding prose.

What is proved. Theorem 1 gives the transfer for uniform quantum adversaries and Theorem 2 for non-uniform ones, whenever the classical security implication is witnessed by a black-box reduction between the games — the implementation reduction may be arbitrary. Theorem 3 covers reductions that assume a deterministic adversary. Corollary 1 assembles them.

Why the hypothesis is there. A black-box security reduction only feeds its adversary inputs and reads its outputs, so it can be run against a quantum adversary as well as a classical one, modulo the care the paper takes over rewinding and over the \(1^{1/\varepsilon}\) parameter. A non-black-box reduction may inspect and transform the adversary’s code, and a transformation designed for classical code has no general reason to do anything meaningful to a quantum algorithm.

Where the statement sits. It is Corollary 1 with the black-box hypothesis removed. The paper does not conjecture an answer, and neither direction has an obvious candidate: a proof would need a general argument covering code-inspecting reductions, and a refutation would need a primitive whose classical implication of one-way functions is genuinely non-black-box — which is itself a short list.

The interest is that this is a question about proofs becoming a question about truth. Nobody doubts that the classical primitives in question exist post-quantumly under reasonable assumptions; what is unclear is whether the implication that made one-way functions minimal is an artifact of the black-box style in which it was proved.

Two boundaries worth keeping straight. This is not about fully quantum cryptography, where the hierarchy is genuinely different — there are oracles relative to which pseudorandom states exist while \(\mathbf{BQP} = \mathbf{QMA}\), and a classical oracle relative to which single-copy pseudorandom states exist while \(\mathbf{P} = \mathbf{NP}\). And it is not about constructivity: the reduction from \(\mathcal{F}\) to \(\mathcal{Q}\) is allowed to be non-constructive throughout; only the security clause’s witness is at issue.

Prove or refute the transfer when the classical security implication is not black-box.
Exhibit a natural primitive whose classical implication of one-way functions is genuinely non-black-box, which would give the question a concrete instance.
Check whether the answer differs between the uniform and non-uniform adversary classes, as it does not in the settled cases.
Confirm the transcription against Definition 5 and Definition 8 of the source, in particular the \(1^{1/\varepsilon}\) parameter and the per-implementation clauses.
Formalize the statement in Lean. Game-based primitives, reductions and the two adversary classes need writing first.

Buxbaum and Mahmoody. A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography. Cryptology ePrint Archive, Report 2024/2095; IACR Communications in Cryptology, 2024. Definitions 5 and 8, Theorems 1, 2 and 3, and Corollary 1 — the statement above is that corollary with its black-box hypothesis removed.
Impagliazzo and Luby. One-way functions are essential for complexity based cryptography. FOCS 1989, pp. 230–235. The classical minimality results.
Reingold, Trevisan, and Vadhan. Notions of reducibility between cryptographic primitives. TCC 2004, LNCS 2951, pp. 1–20. The taxonomy of reductions the hypothesis is stated in.