Paper 2024/1490
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\#\mathsf{P}$Hardness
Abstract
Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from 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, wellstudied mathematical problems that are conjectured to be hard for $\mathsf{P}^{\#\mathsf{P}}$  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 samplingbased quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P}^{\#\mathsf{P}} \not\subseteq \mathsf{(io)BQP}/\mathsf{qpoly}$. Our techniques uncover strong connections between the hardness of approximating the probabilities of outcomes of quantum processes, the existence of ``oneway'' state synthesis problems, and the existence of useful cryptographic primitives such as oneway puzzles and quantum bit commitments. Specifically, we prove that the following hardness assumptions are equivalent under $\mathsf{BQP}$ reductions. 1. The hardness of approximating the probabilities of outcomes of certain efficiently sampleable distributions. That is, there exist quantumly efficiently sampleable distributions for which it is hard to approximate the probability assigned to a randomly chosen string in the support of the distribution (upto inverse polynomial multiplicative error). 2. The existence of oneway puzzles, where a quantum sampler outputs a pair of classical strings  a puzzle and its key  and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. 3. The existence of state puzzles, or oneway state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (oneway puzzles, quantum bit commitments, state puzzles) from concrete, wellfounded mathematical assumptions that do not imply the existence of classical cryptography. Along the way, we also show that distributions that admit efficient quantum samplers but cannot be pseudodeterministically efficiently sampled imply quantum commitments.
Note: Minor changes. Added comparisons with concurrent work.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 quantum advantagequantum cryptographyoneway puzzlesrandom circuitsBosonSamplingstate puzzles
 Contact author(s)

dakshita @ illinois edu
ktomer2 @ illinois edu  History
 20241010: revised
 20240923: received
 See all versions
 Short URL
 https://ia.cr/2024/1490
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1490, author = {Dakshita Khurana and Kabir Tomer}, title = {Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\#\mathsf{P}$Hardness}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1490}, year = {2024}, url = {https://eprint.iacr.org/2024/1490} }