Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness
These are the first constructions of quantum cryptographic primitives from mathematical assumptions that do not imply the existence of one-way functions/classical cryptography, and show that distributions that admit efficient quantum samplers but cannot be pseudo-deterministically efficiently sampled imply quantum commitments.
Abstract
Recent oracle separations [Kretschmer, TQC’21, Kretschmer et. al., STOC’23] have raised the tantalizing possibility of basing quantum cryptography on sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be #P-hard – such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling [Aaronson-Arkhipov, STOC’11], Random Circuit Sampling [Boixo et. al., Nature Physics 2018], IQP [Bremner, Jozsa and Shepherd, Proc. Royal Society of London 2010]) is true, quantum cryptography can be based on the extremely mild (worst-case) complexity assumption that efficient quantum machines cannot decide P^#P. Our techniques uncover strong connections between the hardness of approximating the probabilities of outcomes of quantum processes, the existence of “one-way” state synthesis problems, and the existence of useful cryptographic primitives such as one-way puzzles and quantum bit commitments. Specifically, we prove that the following hardness assumptions are equivalent under quantum polynomial time reductions. Specifically, we prove that the following hardness assumptions are equivalent under quantum polynomial time reductions. - The hardness of approximating the probabilities of outcomes of quantumly efficiently sampleable distributions, upto inverse polynomial relative error. - The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings – a puzzle and its key – and where the hardness lies in finding any key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC’24]. - The existence of state puzzles, or one-way state synthesis problems, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum secrets and classical challenges. These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from mathematical assumptions that do not imply the existence of one-way functions/classical cryptography. Along the way, we also show that distributions that admit efficient quantum samplers but cannot be pseudo-deterministically efficiently sampled imply quantum commitments.