Abstract: In this talk, I will discuss the construction of a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in “Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom quantum states, (2) holds for a random oracle, and thus plausibly holds for existing hash functions like SHA3, and (3) is independent of the P vs. NP question in the black box setting. This offers further evidence that one-way functions are not necessary for computationally-secure quantum cryptography. Our proof builds on recent work of Aaronson, Ingram, and Kretschmer (2022). Based on joint work with Luowen Qian, Makrand Sinha, and Avishay Tal.
Bio: William Kretschmer is a Ph.D. candidate in Computer Science at UT Austin advised by Scott Aaronson. He is broadly interested in quantum complexity theory, including query complexity, structural complexity, pseudorandom quantum states, learning theory, and the stabilizer formalism. In Fall 2023, he will start a postdoc at the Simons Institute.