Quantum Cryptography in Algorithmica

Quantum Cryptography in Algorithmica

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 is PhD candidate at UT Austin, where he works broadly on quantum complexity theory and is advised by Scott Aaronson. Some common topics of study in his research include query complexity, structural complexity, pseudorandom quantum states, learning theory, and the stabilizer formalism, especially as they apply to computational problems involving quantum states and unitary transformations.