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

Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator Avaliação de dureza para problema de pesquisa LWE usando simulador BKZ progressivo

Yuntao WANG, Yoshinori AONO, Tsuyoshi TAKAGI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema de aprendizagem com erros (LWE) é considerado um dos candidatos mais atraentes como base de segurança para criptossistemas pós-quânticos. Para a aplicação de esquemas criptográficos baseados em LWE, são necessários os parâmetros concretos: o comprimento n do vetor secreto, os módulos q e o desvio σ. Em meados de 2016, o grupo alemão TU Darmstadt iniciou o Desafio LWE para avaliar a dureza dos problemas de LWE. Existem várias abordagens para resolver o problema LWE reduzindo o LWE a outros problemas de rede. O grupo de Xu et al. resolveu algumas instâncias do Desafio LWE usando a técnica de enumeração adaptada de Liu-Nguyen (reduzindo o problema de LWE para BDD) [23] e publicaram este resultado no ACNS 2017 [32]. Neste artigo, inicialmente, aplicamos o BKZ progressivo nos casos de desafio LWE de σ/q=0.005 usando a técnica de incorporação de Kannan. Podemos observar intuitivamente que a técnica de incorporação é mais eficiente com o fator de incorporação M mais próximo de 1. Em seguida, analisaremos o número ideal de amostras m para um ataque bem-sucedido ao caso LWE com duração secreta de n. Em terceiro lugar, com base nesta análise, mostramos as estimativas práticas de custos usando o simulador preciso e progressivo BKZ. Simultaneamente, nossos resultados experimentais mostram que para n ≥ 55 e o fixo σ/q=0.005, a técnica de incorporação com BKZ progressivo é mais eficiente do que a implementação do algoritmo de enumeração de Xu et al. Além disso, através da nossa definição de parâmetros, conseguimos resolver o Desafio LWE em (n,σ/q)=(70, 0.005) usando 216.8 segundos (32.73 horas de núcleo único).

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.12 pp.2162-2170
Data de publicação
2018/12/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E101.A.2162
Tipo de Manuscrito
Special Section PAPER (Special Section on Information Theory and Its Applications)
Categoria
Criptografia e Segurança da Informação

autores

Yuntao WANG
  Kyushu University,The University of Tokyo
Yoshinori AONO
  National Institute of Communication and Technology
Tsuyoshi TAKAGI
  The University of Tokyo,Kyushu University

Palavra-chave