In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field (\mathbb{F}2) drawn from a specified distribution. In particular, for any (d \ge 2), we design a distribution of degree up to (d) polynomials ({p_i(x_1,\ldots,x_n)}{i\in[m]}) for (m \lt n) over (\mathbb{F}2) for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves ({p_i(x_1,\ldots,x_n) = y_i}{i\in[m]}) for a random vector ((y_1,\ldots,y_m)). On the other hand, while solutions exist with high probability, we conjecture that for constant (d \gt 2), it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case
NP search problem of finding a solution to a system of (underdetermined) multivariate quadratic equations over the finite field
F2 drawn from a specified distribution. In particular, we design a distribution of degree-2 polynomials
{pi(x1,…,xn)}i∈[m] for $m
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: — There are NP search problems solvable by quantum polynomial-time (QPT) machines but not classical probabilistic polynomial-time (PPT) machines. — There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar counterexamples exist for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the counterexample does not necessarily extend to the case of other cryptographic objects such as PRGs. — There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. — Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant
k-junta testing with high precision can be solved using
poly(k) quantum queries, whereas any classical algorithm requires at least
kΩ(logk) queries.
The problem of tolerant
k-junta testing is as follows: given parameters
(k,ε1,ε2), with
0≤ε1<ε2≤1/2, and black-box access to a Boolean function
f (defined on
n variables), distinguish whether
f is
ε1-close to some
k-junta or
ε2-far from every
k-junta.
We show the quantum advantage for a range of parameters close to
1/2, for example,
ε1=1/2−1/k and
ε2=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most
ε1 to
k-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick
k out of
n coordinates, and for each fixing of the
k coordinates, the
2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to
k-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making
ko(logk) queries.
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.
Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system FS has a solution and compute one if FS does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of FS and the condition number of FS. As a consequence, we give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are small, say polynomial in the size of FS. We apply our quantum algorithm for solving Boolean equations to the cryptanalysis of several important cryptosystems: the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large. This leads to a new criterion for designing cryptosystems that can against the attack of quantum computers: their corresponding equation systems must have large condition numbers.