Posted

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\mathsf{NP} search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field F2\mathbb{F}_2 drawn from a specified distribution. In particular, for any d2d \geq 2, we design a distribution of degree up to dd polynomials {pi(x1,,xn)}i[m]\{p_i(x_1,\ldots,x_n)\}_{i\in [m]} for m<nm<n over F2\mathbb{F}_2 for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves {pi(x1,,xn)=yi}i[m]\{p_i(x_1,\ldots,x_n)=y_i\}_{i\in [m]} for a random vector (y1,,ym)(y_1,\ldots,y_m). On the other hand, while solutions exist with high probability, we conjecture that for constant d>2d > 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\mathbb{F}_2 multivariate polynomials -- those that satisfy 22-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most dd polynomials for any constant d2d \geq 2. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!