An Efficient $F_4$ -style Based Algorithm to Solve MQ Problems
An Efficient $F_4$ -style Based Algorithm to Solve MQ Problems
复制标题
一种高效的基于 $F_4$ 风格的算法来解决 MQ 问题
DOI：
10.1007/978-3-030-26834-3_3
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Uchiyama Shigenori
中科院分区：
文献类型：
--
作者：
Ito Takuma;Shinohara Naoyuki;Uchiyama Shigenori
多变量公钥密码体制是一种很有潜力的后量子密码体制。它的安全性取决于求解有限域上的代数方程组的难度。特别是，多变量二次（MQ）问题是解决这样一个由二次多项式组成的系统，并被视为密码学中的一个重要研究课题。在Fukuoka MQ挑战项目中，讨论了MQ问题的困难性，并报告了MQ问题所使用的算法和由这些算法获得的计算结果。计算MQ问题所给出的多项式集的Gröbner基的算法是为了解决MQ问题。例如，该算法和M4GB算法已经成功地解决了项目提供的多个MQ问题。本文基于风格算法，给出了一个求解Fukuoka MQ挑战项目中生成的稠密多项式MQ问题的有效算法。实验结果表明，该算法比M4GB算法和M4GB算法在求解MQ问题时所需的计算时间和内存更少。当变量个数为36和37时，我们成功地用我们的算法解决了II型问题。
The multivariate public key cryptosystem (MPKC) is a potential post-quantum cryptosystem. Its safety depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and the algorithms used for the MQ problem and the computational results obtained by these algorithms are reported. The algorithms to compute Gröbner basis for the polynomial set given by the MQ problem are for solving the MQ problem. For example, thealgorithm and M4GB algorithm have succeeded in solving several MQ problems provided by the project. In this paper, based on the-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than thealgorithm and M4GB algorithm. We succeeded in solving Type II problems using our algorithm when the numbers of variables are 36 and 37.