La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Solving the MQ Problem Using Gröbner Basis Techniques Résoudre le problème MQ à l'aide des techniques de base de Gröbner

Takuma ITO, Naoyuki SHINOHARA, Shigenori UCHIYAMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.1 pp.135-142
Date de publication
2021/01/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2020CIP0025
Type de manuscrit
Special Section PAPER (Special Section on Cryptography and Information Security)
Catégories

Auteurs

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

Mots-clés

Table des matières