No fully-black-box reduction from PRS to OWF
Statement
No construction of a one-way function secure against quantum adversaries from PRS generators with exponential dimension relativizes with respect to quantum oracles, so in particular none is fully black-box. The oracle is a pair : , where for independent Haar-random -qubit unitaries , ; and is a classical language, constructed recursively and independently of , that accepts the description of a verifier with oracle access to exactly when the verifier runs in time less than and the average, over Haar-random unitaries in place of , of its maximum acceptance probability over witnesses exceeds . With probability over , relative to , and is a family of pseudorandom unitaries with , which gives PRS generators with -bit keys and output length , so exponential dimension with — Kre21. Relative to that oracle every function computable in bounded-error quantum polynomial time with oracle access is inverted in quantum polynomial time: whether a preimage with a given prefix exists is decided in , and a search over prefixes finds one — standard.
Notes
- The pseudorandom unitaries are proved secure against polynomial-time quantum adversaries with classical advice — Kre21.
- The conference version of Kre21 took to be an arbitrary -complete language; its proof that relative to that pair has an error, and the arXiv version replaces by the language above. Whether the pair with a -complete also works is conjectured, not proved — Kre21.
- A fully-black-box reduction from PRS to OWF would give one from exponential-dimension PRS through Exponential-dimension PRS ⇒ PRS, so none exists from PRS either — standard.
- Relative to a classical oracle, and single-copy-secure PRS generators with , secure against uniform quantum adversaries, exist (No relativizing reduction from single-copy PRS to OWF) — KQST23.
- PRS generators with do not exist if — Kre21.
- The other direction holds: one-way functions secure against quantum adversaries yield PRS generators — JLS18.