No relativizing reduction from single-copy PRS to OWF

Unconditional · against relativizing reductions · KQST23

Statement

No construction of a one-way function from single-copy-secure PRS generators relativizes: there is a classical oracle relative to which and single-copy-secure PRS generators with , secure against uniform quantum adversaries, exist — KQST23. KQST23 consider only uniform adversaries, so the barrier is for the uniform reading of single-copy security (uniform and non-uniform adversaries) — KQST23. Relative to that oracle every function computable in polynomial time with oracle access is inverted in polynomial time: whether a preimage with a given prefix exists is decided in , and a search over prefixes finds one — standard.