Quantum-secure OWF ⇒ PRS

Quantum setting · JLS18

Statement

If one-way functions secure against efficient quantum adversaries exist, then pseudorandom quantum state generators exist for every polynomial output length , in particular with output length linear in the key — JLS18. The construction outputs the pseudorandom phase state

for a pseudorandom function that is secure against quantum adversaries querying it in superposition: by JLS18 Theorem 1 (arXiv 1711.00385v1), for every such pseudorandom function the family is a PRS, with and functions of for which the pseudorandom function exists and superpolynomial in , which the statistical step of the proof (JLS18 Lemma 2) needs; taking -bit keys and gives output length linear in the key.

Notes

  • For the random phase states are and . Measuring two copies in the basis gives equal outcomes with probability , against for a Haar-random qubit. In general, a random phase state gives uniform outcomes in the computational basis, so two copies collide with probability , against for a Haar-random state, and copies tell the two apart; the construction therefore needs — standard.
  • A pseudorandom function secure against superposition queries exists if quantum-secure one-way functions do: the GGM construction from a quantum-secure pseudorandom generator is secure against such queries — Zha12.
  • The converse fails relative to a quantum oracle, under which PRS generators exist and no quantum-secure one-way function does — Kre21; see No fully-black-box reduction from PRS to OWF.