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
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).
Yuntao WANG
Kyushu University,The University of Tokyo
Yoshinori AONO
National Institute of Communication and Technology
Tsuyoshi TAKAGI
The University of Tokyo,Kyushu University
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
Yuntao WANG, Yoshinori AONO, Tsuyoshi TAKAGI, "Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 12, pp. 2162-2170, December 2018, doi: 10.1587/transfun.E101.A.2162.
Abstract: The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length n of secret vector, the moduli q and the deviation σ. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of σ/q=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor M closer to 1. Then we will analyze the optimal number of samples m for a successful attack on LWE case with secret length of n. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for n ≥ 55 and the fixed σ/q=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (n,σ/q)=(70, 0.005) using 216.8 seconds (32.73 single core hours).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.2162/_p
Copiar
@ARTICLE{e101-a_12_2162,
author={Yuntao WANG, Yoshinori AONO, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator},
year={2018},
volume={E101-A},
number={12},
pages={2162-2170},
abstract={The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length n of secret vector, the moduli q and the deviation σ. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of σ/q=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor M closer to 1. Then we will analyze the optimal number of samples m for a successful attack on LWE case with secret length of n. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for n ≥ 55 and the fixed σ/q=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (n,σ/q)=(70, 0.005) using 216.8 seconds (32.73 single core hours).},
keywords={},
doi={10.1587/transfun.E101.A.2162},
ISSN={1745-1337},
month={December},}
Copiar
TY - JOUR
TI - Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2162
EP - 2170
AU - Yuntao WANG
AU - Yoshinori AONO
AU - Tsuyoshi TAKAGI
PY - 2018
DO - 10.1587/transfun.E101.A.2162
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2018
AB - The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length n of secret vector, the moduli q and the deviation σ. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of σ/q=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor M closer to 1. Then we will analyze the optimal number of samples m for a successful attack on LWE case with secret length of n. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for n ≥ 55 and the fixed σ/q=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (n,σ/q)=(70, 0.005) using 216.8 seconds (32.73 single core hours).
ER -