In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case 𝖭𝖯 search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field 𝔽2 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 m2, 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 𝔽2 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.
