[Resource Topic] 2023/1650: An Efficient Algorithm for Solving the MQ Problem using Hilbert Series

Welcome to the resource topic for 2023/1650

An Efficient Algorithm for Solving the MQ Problem using Hilbert Series

Authors: Kosuke Sakata, Tsuyoshi Takagi


The security of multivariate polynomial cryptography depends on the computational complexity of solving a multivariate quadratic polynomial system (MQ problem). One of the fastest algorithms for solving the MQ problem is F4, which computes a Groebner basis but requires numerous calculations of zero reduction that do not affect the output.The Hilbert-driven algorithm evaluates the number of generators in the Groebner basis of degree d using Hilbert series, then it reduces the number of zero reduction computations. In this paper, we propose a high-speed algorithm designed for randomly generated semi-regular MQ problems. Although the Hilbert-driven algorithm is limited to computing homogeneous ideals, we demonstrate its applicability to semi-regular non-homogeneous ideals in this work. Furthermore, when using the Hilbert-driven algorithm to solve non-homogeneous MQ problems with F4, we demonstrate the efficient achievement of reducing zero reduction for F4. We implemented the proposed algorithm in C++ and report successful decryption of a new record m=21 Type VI equations. This was achieved using an AMD EPYC 7742 processor and 2TB RAM, and the decryption process was completed within approximately 9 h.

ePrint: https://eprint.iacr.org/2023/1650

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .