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

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
post-quantum cryptographymultivariate cryptographyMQ problemGroebner 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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.