Quantum-Computable One-Way Functions without One-Way Functions

We construct a classical oracle relative to which P = NP but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthening of the result of Kretschmer, Qian, Sinha, and Tal (STOC 2023), which only achieved single-copy pseudorandom quantum states relative to an oracle that collapses NP to P . For example, our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes relative to an oracle on which P = NP . Hence, in our new relativized world, classical computers live in ”Algorithmica” whereas quantum computers live in ”Cryptomania,” using the language of Impagliazzo’s worlds. Our proof relies on a new distributional block-insensitivity lemma for AC 0 circuits, wherein a single block is resampled from an arbitrary distribution.

Authors

• William Kretschmer
• Luowen Qian
• Avishay Tal

Keywords

• Algorithmica
• Cryptomania
• Forrelation
• oracles
• quantum-computable one-way functions