Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai (Sep 10 2025).
Abstract: 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
F2 drawn from a specified distribution. In particular, for any
d≥2, we design a distribution of degree up to
d polynomials
{pi(x1,…,xn)}i∈[m] for
m<n over
F2 for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves
{pi(x1,…,xn)=yi}i∈[m] for a random vector
(y1,…,ym). On the other hand, while solutions exist with high probability, we conjecture that for constant
d>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. Our approach begins with the breakthrough Yamakawa-Zhandry (FOCS 2022) quantum algorithmic framework. In our work, we demonstrate that this quantum algorithmic framework extends to the setting of multivariate polynomial systems. Our key technical contribution is a new analysis on the Fourier spectra of distributions induced by a general family of distributions over
F2 multivariate polynomials -- those that satisfy
2-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most
d polynomials for any constant
d≥2. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.