The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le cryptosystème à clé publique multivariée (MPKC) est l'un des principaux cryptosystèmes post-quantiques (PQC), et le National Institute of Standards and Technology (NIST) a récemment sélectionné quatre MPKC comme candidats à son PQC. La sécurité de MPKC dépend de la difficulté de résoudre des systèmes d’équations algébriques sur des corps finis. En particulier, le problème quadratique multivarié (MQ) consiste à résoudre un tel système constitué de polynômes quadratiques et est considéré comme un sujet de recherche important en cryptographie. Dans le projet Fukuoka MQ challenge, la difficulté du problème MQ est discutée et les algorithmes permettant de résoudre le problème MQ ainsi que les résultats de calcul obtenus par ces algorithmes sont rapportés. Les algorithmes de calcul sur la base de Gröbner sont utilisés comme principaux outils pour résoudre le problème MQ. Par exemple, le F4 L'algorithme et l'algorithme M4GB ont réussi à résoudre de nombreuses instances du problème MQ fourni par le projet. Dans cet article, basé sur F4-style algorithme, nous présentons un algorithme efficace pour résoudre les problèmes MQ avec des polynômes denses générés dans le projet de défi Fukuoka MQ. Nous montrons expérimentalement que notre algorithme nécessite moins de temps de calcul et de mémoire pour ces problèmes MQ que le F4 algorithme et algorithme M4GB. Nous avons réussi à résoudre les problèmes de type II et III du défi Fukuoka MQ en utilisant notre algorithme lorsque le nombre de variables était de 37 dans les deux problèmes.
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
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020CIP0025/_p
Copier
@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 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.},
keywords={},
doi={10.1587/transfun.2020CIP0025},
ISSN={1745-1337},
month={January},}
Copier
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 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.
ER -