Complexity estimates for underdetermined MQ systems

[Hiroki Furue]

Dear all,

 

I would like to share a draft manuscript on algorithms for solving underdetermined MQ systems and their application to the security evaluation of multivariate signature schemes.

 

We propose an algorithm for solving underdetermined MQ systems by extending the variable-partitioning technique used in Hashimoto’s method. The proposed algorithm partitions the variables into a larger number of groups and reduces the original system to smaller MQ subproblems.

 

Our complexity evaluation shows that, in the classical setting, the proposed method reduces the estimated direct-attack complexity for MAYO1 from 2^{156} to 2^{145}. In the quantum setting, the proposed method gives smaller estimates than existing algorithms for several parameter sets of multivariate signature schemes that have advanced to the third-round.

 

A draft is available here:

https://eprint.iacr.org/2026/1054

 

Best regards,

Hideki Asanuma, Yilong Chen, Hiroki Furue, Kosuke Sakata, Tsuyoshi Takagi