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
A dureza do problema de decodificação da síndrome (SDP) é a principal evidência da segurança dos criptossistemas baseados em código, que são um dos finalistas em um projeto para padronizar a criptografia pós-quântica conduzido pelo Instituto Nacional de Padrões e Tecnologia dos EUA (NIST -PQC). A decodificação do conjunto de informações (ISD) é um termo geral para algoritmos que resolvem o SDP com eficiência. Neste artigo, conduzimos uma análise concreta da complexidade de tempo dos mais recentes algoritmos ISD sob a limitação de memória usando o estimador de decodificação de síndrome proposto por Esser et al. Como resultado, apresentamos que ISDs teoricamente não ideais, como May-Meurer-Thomae (MMT) e May-Ozerov, têm menor complexidade de tempo do que outros ISDs em algumas instâncias reais de SDP. Com base nesses fatos, estudamos ainda a possibilidade de paralelização múltipla para esses ISDs e propusemos o primeiro algoritmo GPU para MMT, o algoritmo MMT multiparalelo. Nos experimentos, mostramos que o algoritmo MMT multiparalelo é mais rápido que os algoritmos ISD existentes. Além disso, relatamos as primeiras tentativas bem-sucedidas de resolver as instâncias SDP de 510, 530, 540 e 550 dimensões no concurso Decoding Challenge usando o MMT multiparalelo.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -