Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator

Yuntao WANG  Yoshinori AONO  Tsuyoshi TAKAGI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.12   pp.2162-2170
Publication Date: 2018/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.2162
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
Keyword: 
lattice,  LWE challenge,  BDD,  unique SVP,  embedding technique,  progressive BKZ simulator,  post-quantum cryptography,  

Full Text: PDF(1.2MB)
>>Buy this Article


Summary: 
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).