News

Press Releases

An Efficient Variant of F4 Algorithm for Solving MQ Problem

Project Researcher Kosuke Sakata and Professor Tsuyoshi Takagi (Graduate School of Information Science and Technology, The University of Tokyo), have developed a new algorithm for efficiently solving the MQ (Multivariate Quadratic) problem, a key challenge in evaluating next-generation cryptographic security.
The MQ problem involves solving systems of multivariate quadratic equations and plays an important role in assessing the security of post-quantum cryptography, which is designed to remain secure even against quantum computer attacks. However, conventional methods face a major bottleneck due to the extremely large matrices generated during computation.
In this research, they introduced a novel approach using the Hilbert series to identify only the combinations required for computation, keeping matrix sizes small throughout the process. This enabled them to solve an MQ problem estimated to be about 47,000 times more difficult than the previous record.

Successfully solved an MQ problem estimated to be approximately 47,000 times more difficult than those solved by previous methods.

This achievement has been accepted for presentation at CHES 2026 (Cryptographic Hardware and Embedded Systems), a leading international conference in cryptography. The proposed method is expected to contribute to the secure design and security evaluation of post-quantum cryptographic systems in the future.

The research results were published online in IACR Transactions on Cryptographic Hardware and Embedded Systems 2026 (TCHES2026) on July 17, 2026.

Publication Information

Journal：IACR Transactions on Cryptographic Hardware and Embedded Systems 2026 (TCHES2026)
Title：An Efficient Variant of F4 Algorithm for Solving MQ Problem
Authors： Kosuke Sakata, Tsuyoshi Takagi
DOI: https://doi.org/10.46586/tches.v2026.i3.1284-1309
URL: https://tches.iacr.org/index.php/TCHES/article/view/13150

(This English article was translated with the assistance of AI.)