Paper 2023/1650
An Efficient Algorithm for Solving the MQ Problem using Hilbert Series
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
-
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},
note = {\url{https://eprint.iacr.org/2023/1650}},
url = {https://eprint.iacr.org/2023/1650}
}
