An Efficient Algorithm for Solving the MQ Problem using Hilbert Series

Kosuke Sakata; Tsuyoshi Takagi

Paper 2023/1650

An Efficient Algorithm for Solving the MQ Problem using Hilbert Series

Kosuke Sakata, The University of Tokyo

Tsuyoshi Takagi, The University of Tokyo

Abstract

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 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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: post-quantum cryptography multivariate cryptography MQ problem Groebner basis
Contact author(s): sakata-kosuke-rb @ g ecc u-tokyo ac jp
takagi @ g ecc u-tokyo ac jp
History: 2023-10-26: approved; 2023-10-25: received; See all versions
Short URL: https://ia.cr/2023/1650
License: CC0

BibTeX

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