Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
AI Summary
Can average-case NP hardness coexist with the absence of quantum cryptography, even though quantum primitives need not imply classical one-way functions? This paper constructs relativized “Quantum Pessiland” worlds answering this question affirmatively.
A classical oracle supports a language in $\mathsf{UP}\cap\mathsf{coUP}$ whose prediction success on uniformly random inputs is at most $1/2+\operatorname{negl}(n)$ for quantum polynomial-time algorithms with polynomial-size, oracle-dependent quantum advice. It also supports average-case-hard $\mathsf{TFUP}$ search, while $\mathsf{SampBQP}=\mathsf{SampBPP}$ and classically secure auxiliary-input one-way puzzles do not exist. A separate construction using a quantum unitary oracle preserves these hardness properties while ruling out auxiliary-input EFI pairs, thereby excluding the many cryptographic primitives that imply them. The classical construction also gives a relativization barrier to deriving one-way puzzles solely from $\mathsf{P}^{\#\mathsf{P}}\not\subseteq\mathsf{i.o.BQP/qpoly}$.
Both constructions use verification access to random permutations. Hardness follows from quantum-advice permutation-inversion bounds and a quantum Goldreich–Levin reduction. The main technical tool is a uniform patching lemma: an efficient extractor learns polynomially many positive oracle entries that approximate a generator’s output within any prescribed inverse-polynomial trace distance, simultaneously for every sufficiently long auxiliary input. An exponential-moment bound controls the maximum error across inputs. A PSPACE-complete oracle enables classical simulation and conditional sampling; a stratified Helstrom oracle breaks EFI pairs.
These are oracle separations, not unrelativized impossibility results. Whether a classical oracle suffices to rule out EFI pairs remains unresolved. The construction also does not establish an infinite polynomial-time hierarchy.
Little sign of AI-generated textAI use disclosed
We used Claude Fable 5 to assist with writing proofs and Introduction, and ChatGPT-5.6 Sol for proofreading.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which UP∩coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which UP∩coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of UP∩coUP implies P#P⊆i.o.BQP/qpoly, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from P#P⊆i.o.BQP/qpoly, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
Can average-case NP hardness coexist with the absence of quantum cryptography, even though quantum primitives need not imply classical one-way functions? This paper constructs relativized “Quantum Pessiland” worlds answering this question affirmatively.
A classical oracle supports a language in UP∩coUP whose prediction success on uniformly random inputs is at most 1/2+negl(n) for quantum polynomial-time algorithms with polynomial-size, oracle-dependent quantum advice. It also supports average-case-hard TFUP search, while SampBQP=SampBPP and classically secure auxiliary-input one-way puzzles do not exist. A separate construction using a quantum unitary oracle preserves these hardness properties while ruling out auxiliary-input EFI pairs, thereby excluding the many cryptographic primitives that imply them. The classical construction also gives a relativization barrier to deriving one-way puzzles solely from P#P⊆i.o.BQP/qpoly.
Both constructions use verification access to random permutations. Hardness follows from quantum-advice permutation-inversion bounds and a quantum Goldreich–Levin reduction. The main technical tool is a uniform patching lemma: an efficient extractor learns polynomially many positive oracle entries that approximate a generator’s output within any prescribed inverse-polynomial trace distance, simultaneously for every sufficiently long auxiliary input. An exponential-moment bound controls the maximum error across inputs. A PSPACE-complete oracle enables classical simulation and conditional sampling; a stratified Helstrom oracle breaks EFI pairs.
These are oracle separations, not unrelativized impossibility results. Whether a classical oracle suffices to rule out EFI pairs remains unresolved. The construction also does not establish an infinite polynomial-time hierarchy.
One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Microcrypt'' where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs. In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class, SampPDQP, which is a sampling version of the decision class PDQP introduced in [Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]. We show that if SampPDQP is hard on average for quantum polynomial time, then OWPuzzs exist. SampPDQP is the class of sampling problems that can be solved by a classical polynomial-time algorithm that can make a single query to a non-collapsing measurement oracle, which is a ''magical'' oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial-time. We also study upperbounds of the hardness of SampPDQP. We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing [Dubrov and Ishai, STOC 2006]. We show that dCRPuzzs imply average-case hardness of SampPDQP (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot signatures [Amos, Georgiou, Kiayias, Zhandry, STOC 2020] imply dCRPuzzs.
The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies PP=BQP, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from P=NP-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to P=NP. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from PP=BQP. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from PP=BQP. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then SampBQP=SampBPP follows from the infiniteness of the polynomial hierarchy. Despite that, we show that PP=BQP is equivalent to another standard notion of hardness of learning: agnostic. We prove that PP=BQP if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against PPTΣ3P learners implies SampBQP=SampBPP.
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P-Hardness
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, well-studied mathematical problems that are conjectured to be hard for P#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 sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that P#P⊆(io)BQP/qpoly. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) 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 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 one-way 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 (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
We construct a classical oracle relative to which P=NP but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthening of the result of Kretschmer, Qian, Sinha, and Tal (STOC 2023), which only achieved single-copy pseudorandom quantum states relative to an oracle that collapses NP to P. For example, our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes relative to an oracle on which P=NP. Hence, in our new relativized world, classical computers live in "Algorithmica" whereas quantum computers live in "Cryptomania," using the language of Impagliazzo's worlds. Our proof relies on a new distributional block-insensitivity lemma for AC0 circuits, wherein a single block is resampled from an arbitrary distribution.
We construct a unitary oracle relative to which BQP=QCMA but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive key exchange exist. We also construct a unitary oracle relative to which BQP=QMA, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which BQP=QMA but pseudorandm unitaries exist. We also show that (poly-round) QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of ``quantum samplable'' one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if BQP=PP. Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if BQP=QCMA, but are broken if BQP=PP. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class ``CountCrypt''.