Paper 2026/1054

Improved Complexity Estimates for Underdetermined MQ Systems via Generalized Variable Partitioning

Abstract

Multivariate quadratic (MQ) signature schemes are an important class of post-quantum digital signatures. These schemes rely on the hardness of solving underdetermined MQ systems, where the number of variables \(n\) exceeds the number of equations \(m\). Therefore, analyzing the efficiency of algorithms for underdetermined MQ systems is essential for evaluating the security of MQ-based signature schemes. Several algorithms have been proposed to solve underdetermined MQ systems efficiently. Among them, Hashimoto's method is one of the best known partition-based direct attacks; it partitions the variables into three groups and reduces the original problem to two smaller MQ subproblems. In this paper, we propose a generalized partition-based algorithm for solving underdetermined MQ systems. The proposed algorithm extends Hashimoto's method by partitioning the variables into more groups and reducing the original problem to smaller MQ subproblems. We derive its applicability conditions and time complexity, and develop an efficient parameter search strategy to find the best partition parameters without a naive exhaustive search. Finally, we evaluate the proposed algorithm on parameter sets of MAYO, QR-UOV, and SNOVA, and compare the resulting estimates with those of existing algorithms for underdetermined MQ systems. In the classical case, the proposed method improves on Hashimoto's method for some parameter sets; in particular, it reduces the estimate for MAYO1 from \(2^{156}\) to \(2^{145}\). In the quantum case, the proposed method gives estimates smaller than both Just Guess and Hashimoto's method for many parameter sets.