איתי דינור

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 F₂ drawn from a specified distribution. In particular, for any d ≥ 2, we design a distribution of degree up to d polynomials {p_i(x₁, . . ., x_n)}_i∈[m] for m < n over F₂ for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves {p_i(x₁, . . ., x_n) = y_i}_i∈[m] for a random vector (y₁, . . ., y_m). 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 F₂ 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.