Paper 2023/1650

An Efficient Variant of F4 Algorithm for Solving MQ Problem

Tsuyoshi Takagi, The University of Tokyo

Abstract

In this paper, we propose an enhanced variant of the F4 algorithm specifically designed for efficiently solving multivariate quadratic (MQ) problems, which are central to many post-quantum cryptographic schemes. Our approach overcomes a major inefficiency of conventional F4 by integrating a Hilbert-driven strategy that determines the optimal number of S-polynomials to generate at each degree, thereby reducing unnecessary zero reductions. We further introduce refined pair selection techniques that prioritize candidates yielding S-polynomials with smaller leading terms, which in turn minimizes the dimensions of intermediate matrices used during reduction. Experimental results show that our implementation outperforms state-of-the-art systems such as M4GB and Magma's F4 in both single-core and multi-core environments. Notably, our method sets new records in the Fukuoka MQ Challenge for Type VI problems over F(31) with m = 21,22,23,24 demonstrating the robustness and practical impact of our approach in solving highly challenging MQ instances. According to the computational complexity estimation formula], the problem with m = 24 is approximately 47,627 times harder than the previous record case with m = 20.

@misc{cryptoeprint:2023/1650,
      author = {Kosuke Sakata and Tsuyoshi Takagi},
      title = {An Efficient Variant of F4 Algorithm for Solving {MQ} Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1650},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1650}
}