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
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.
Shintaro NARISADA
KDDI Research, Inc.
Kazuhide FUKUSHIMA
KDDI Research, Inc.
Shinsaku KIYOMOTO
KDDI Research, Inc.
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
Shintaro NARISADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, "Multiparallel MMT: Faster ISD Algorithm Solving High-Dimensional Syndrome Decoding Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 241-252, March 2023, doi: 10.1587/transfun.2022CIP0023.
Abstract: The hardness of the syndrome decoding problem (SDP) is the primary evidence for the security of code-based cryptosystems, which are one of the finalists in a project to standardize post-quantum cryptography conducted by the U.S. National Institute of Standards and Technology (NIST-PQC). Information set decoding (ISD) is a general term for algorithms that solve SDP efficiently. In this paper, we conducted a concrete analysis of the time complexity of the latest ISD algorithms under the limitation of memory using the syndrome decoding estimator proposed by Esser et al. As a result, we present that theoretically nonoptimal ISDs, such as May-Meurer-Thomae (MMT) and May-Ozerov, have lower time complexity than other ISDs in some actual SDP instances. Based on these facts, we further studied the possibility of multiple parallelization for these ISDs and proposed the first GPU algorithm for MMT, the multiparallel MMT algorithm. In the experiments, we show that the multiparallel MMT algorithm is faster than existing ISD algorithms. In addition, we report the first successful attempts to solve the 510-, 530-, 540- and 550-dimensional SDP instances in the Decoding Challenge contest using the multiparallel MMT.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022CIP0023/_p
Copier
@ARTICLE{e106-a_3_241,
author={Shintaro NARISADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Multiparallel MMT: Faster ISD Algorithm Solving High-Dimensional Syndrome Decoding Problem},
year={2023},
volume={E106-A},
number={3},
pages={241-252},
abstract={The hardness of the syndrome decoding problem (SDP) is the primary evidence for the security of code-based cryptosystems, which are one of the finalists in a project to standardize post-quantum cryptography conducted by the U.S. National Institute of Standards and Technology (NIST-PQC). Information set decoding (ISD) is a general term for algorithms that solve SDP efficiently. In this paper, we conducted a concrete analysis of the time complexity of the latest ISD algorithms under the limitation of memory using the syndrome decoding estimator proposed by Esser et al. As a result, we present that theoretically nonoptimal ISDs, such as May-Meurer-Thomae (MMT) and May-Ozerov, have lower time complexity than other ISDs in some actual SDP instances. Based on these facts, we further studied the possibility of multiple parallelization for these ISDs and proposed the first GPU algorithm for MMT, the multiparallel MMT algorithm. In the experiments, we show that the multiparallel MMT algorithm is faster than existing ISD algorithms. In addition, we report the first successful attempts to solve the 510-, 530-, 540- and 550-dimensional SDP instances in the Decoding Challenge contest using the multiparallel MMT.},
keywords={},
doi={10.1587/transfun.2022CIP0023},
ISSN={1745-1337},
month={March},}
Copier
TY - JOUR
TI - Multiparallel MMT: Faster ISD Algorithm Solving High-Dimensional Syndrome Decoding Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 241
EP - 252
AU - Shintaro NARISADA
AU - Kazuhide FUKUSHIMA
AU - Shinsaku KIYOMOTO
PY - 2023
DO - 10.1587/transfun.2022CIP0023
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2023
AB - The hardness of the syndrome decoding problem (SDP) is the primary evidence for the security of code-based cryptosystems, which are one of the finalists in a project to standardize post-quantum cryptography conducted by the U.S. National Institute of Standards and Technology (NIST-PQC). Information set decoding (ISD) is a general term for algorithms that solve SDP efficiently. In this paper, we conducted a concrete analysis of the time complexity of the latest ISD algorithms under the limitation of memory using the syndrome decoding estimator proposed by Esser et al. As a result, we present that theoretically nonoptimal ISDs, such as May-Meurer-Thomae (MMT) and May-Ozerov, have lower time complexity than other ISDs in some actual SDP instances. Based on these facts, we further studied the possibility of multiple parallelization for these ISDs and proposed the first GPU algorithm for MMT, the multiparallel MMT algorithm. In the experiments, we show that the multiparallel MMT algorithm is faster than existing ISD algorithms. In addition, we report the first successful attempts to solve the 510-, 530-, 540- and 550-dimensional SDP instances in the Decoding Challenge contest using the multiparallel MMT.
ER -