Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ Problem

We propose a novel algorithm to solve underdetermined systems of multivariate quadratic (MQ) equations over finite fields. In modern MQ signature schemes such as MAYO, QR-UOV and SNOVA finding solutions to such systems is equivalent to signature forgery.

The current benchmark for estimating forgery bit complexity is Hashimoto’s algorithm which transforms the original underdetermined MQ system $P$ into a more tractable system $\tilde{P}$. A hybrid combination of solving $\tilde{P}$ via Gröbner basis and exhaustive search eventually solves $P$.

We introduce a novel transformation that pushes the hybrid approach to its extreme. Specifically, we reduce the underdetermined MQ system to a sequence of quadratic equations in a single variable at the cost of a larger exhaustive search. As a consequence, signature forgery no longer relies on the hardness of MQ solving but becomes pure guessing via exhaustive search. This in turn implies that signature forgery is significantly more vulnerable against quantum attacks via Grover search.

We provide accurate estimates for the classical and quantum bit complexity of forging signatures for MAYO, QR-UOV and SNOVA using our novel algorithm. We reduce the quantum security of all security levels of MAYO, QR-UOV and SNOVA.