Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P-Hardness

Dakshita Khuarna (University of Illinois Urbana-Champaign) https://simons.berkeley.edu/talks/dakshita-khuarna-university-illinois-urbana-champaign-2025-05-29 Quantum Algorithms, Complexity, and Fault Tolerance Reunion A flurry of exciting recent research has shown that quantum cryptosystems (beyond QKD) can exist relative to certain oracles that break all classical cryptography. But obtaining unrelativized constructions of quantum cryptosystems from assumptions clearly weaker than the existence of one-way functions remained open. In this talk, I will describe how​ to base quantum commitments and secure computation on concrete and well-studied mathematical assumptions, from the quantum advantage literature, that do not imply the existence of one-way functions.