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

Multiparallel MMT: Faster ISD Algorithm Solving High-Dimensional Syndrome Decoding Problem MMT multiparallèle : un algorithme ISD plus rapide résolvant le problème de décodage du syndrome de haute dimension

Shintaro NARISADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO

  • Vues en texte intégral

    0

  • Citer

Résumé:

La dureté du syndrome de décodage problème (SDP) est la principale preuve de la sécurité des cryptosystèmes basés sur le code, qui sont l'un des finalistes d'un projet de normalisation de la cryptographie post-quantique mené par l'Institut national américain des normes et de la technologie (NIST). -PQC). Le décodage d'ensemble d'informations (ISD) est un terme général désignant les algorithmes qui résolvent efficacement le SDP. Dans cet article, nous avons effectué une analyse concrète de la complexité temporelle des derniers algorithmes ISD sous limitation de mémoire en utilisant l'estimateur de décodage de syndrome proposé par Esser et al. En conséquence, nous présentons que les ISD théoriquement non optimaux, tels que May-Meurer-Thomae (MMT) et May-Ozerov, ont une complexité temporelle inférieure à celle des autres ISD dans certaines instances SDP réelles. Sur la base de ces faits, nous avons étudié plus en détail la possibilité de parallélisation multiple pour ces ISD et proposé le premier algorithme GPU pour MMT, l'algorithme MMT multiparallèle. Dans les expériences, nous montrons que l’algorithme MMT multiparallèle est plus rapide que les algorithmes ISD existants. De plus, nous rapportons les premières tentatives réussies de résolution des instances SDP à 510, 530, 540 et 550 dimensions dans le cadre du concours Decoding Challenge à l'aide du MMT multiparallèle.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.241-252
Date de publication
2023/03/01
Publicisé
2022/11/09
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2022CIP0023
Type de manuscrit
Special Section PAPER (Special Section on Cryptography and Information Security)
Catégories

Auteurs

Shintaro NARISADA
  KDDI Research, Inc.
Kazuhide FUKUSHIMA
  KDDI Research, Inc.
Shinsaku KIYOMOTO
  KDDI Research, Inc.

Mots-clés

Table des matières