Solving the MQ Problem Using Gröbner Basis Techniques

Takuma ITO; Naoyuki SHINOHARA; Shigenori UCHIYAMA

doi:10.1587/transfun.2020CIP0025

IEICE TRANSACTIONS on Fundamentals

Solving the MQ Problem Using Gröbner Basis Techniques

Takuma ITO, Naoyuki SHINOHARA, Shigenori UCHIYAMA

Full Text Views

0

Cite this

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 F₄ algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F₄-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 F₄ 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.1 pp.135-142

Publication Date: 2021/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2020CIP0025

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Authors

Takuma ITO
  National Institute of Information and Communications Technology,Tokyo Metropolitan University
Naoyuki SHINOHARA
  National Institute of Information and Communications Technology
Shigenori UCHIYAMA
  Tokyo Metropolitan University

Keyword

multivariate public key cryptosystems, post-quantum cryptography, multivariate quadratic problem, Gröbner basis, F₄-style algorithm

Cite this

Copy

Takuma ITO, Naoyuki SHINOHARA, Shigenori UCHIYAMA, "Solving the MQ Problem Using Gröbner Basis Techniques" in IEICE TRANSACTIONS on Fundamentals, vol. E104-A, no. 1, pp. 135-142, January 2021, doi: 10.1587/transfun.2020CIP0025.
Abstract: 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 F₄ algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F₄-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 F₄ 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020CIP0025/_p

Copy

@ARTICLE{e104-a_1_135,
author={Takuma ITO, Naoyuki SHINOHARA, Shigenori UCHIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Solving the MQ Problem Using Gröbner Basis Techniques},
year={2021},
volume={E104-A},
number={1},
pages={135-142},
abstract={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 F₄ algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F₄-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 F₄ 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.},
keywords={},
doi={10.1587/transfun.2020CIP0025},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Solving the MQ Problem Using Gröbner Basis Techniques
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 135
EP - 142
AU - Takuma ITO
AU - Naoyuki SHINOHARA
AU - Shigenori UCHIYAMA
PY - 2021
DO - 10.1587/transfun.2020CIP0025
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2021
AB - 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 F₄ algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F₄-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 F₄ 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.
ER -

IEICE TRANSACTIONS on Fundamentals