Solving the MQ Problem Using Gröbner Basis Techniques

Takuma ITO  Naoyuki SHINOHARA  Shigenori UCHIYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.1   pp.135-142
Publication Date: 2021/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020CIP0025
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
multivariate public key cryptosystems,  post-quantum cryptography,  multivariate quadratic problem,  Gröbner basis,  F4-style algorithm,  

Full Text: PDF(771KB)>>
Buy this Article




Summary: 
Multivariate public key cryptosystem (MPKC) is one of the major post quantum cryptosystems (PQC), and the National Institute of Standards and Technology (NIST) recently selected four MPKCs as candidates of their PQC. The security of MPKC 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 algorithms for solving the MQ problem and the computational results obtained by these algorithms are reported. Algorithms for computing Gröbner basis are used as the main tools for solving the MQ problem. For example, the F4 algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F4-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 the F4 algorithm and M4GB algorithm. We succeeded in solving Type II and III problems of Fukuoka MQ challenge using our algorithm when the number of variables was 37 in both problems.