A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 multiparalelo: algoritmo ISD mais rápido resolvendo problema de decodificação de síndrome de alta dimensão

Shintaro NARISADA, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.241-252
Data de publicação
2023/03/01
Publicitada
2022/11/09
ISSN online
1745-1337
DOI
10.1587/transfun.2022CIP0023
Tipo de Manuscrito
Special Section PAPER (Special Section on Cryptography and Information Security)
Categoria

autores

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

Palavra-chave