2026-07-22 東京大学
従来より約47,000倍難しいとされるMQ問題を解読
＜関連情報＞
- https://www.i.u-tokyo.ac.jp/news/press/2026/202607222824.shtml
- https://tches.iacr.org/index.php/TCHES/article/view/13150
MQ問題を解決するためのF4アルゴリズムの効率的な変種 An Efficient Variant of F4 Algorithm for Solving MQ Problem
Kosuke Sakata Tsuyoshi Takagi
IACR Transactions on Cryptographic Hardware and Embedded Systems 2026 Published:2026-07-17
DOI:https://doi.org/10.46586/tches.v2026.i3.1284-1309
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 F31 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 given in [24], the problem with m = 24 is approximately 47,627 times harder than the previous record case with m = 20.
