Cryptology ePrint Archive: Report 2015/1026

Hardness Estimation of LWE via Band Pruning

Yoshinori Aono and Le Trieu Phong and Lihua Wang

Abstract: This paper, examining the hardness of the search LWE problem, is a refined continuation of previous works including (Lindner-Peikert 2011, Liu-Nguyen 2013, Aono et al. 2013) using lattice reduction and lattice vector enumeration. We adopt the attack to the LWE using discrete Gaussian distribution, and propose a new bounding method named band pruning in lattice enumeration. We update the security estimations for several parameter sets proposed in the literature. Finally, using the data gained in our experiments, we derive an explicit formula linking the LWE's parameters with the bit security.

Category / Keywords: foundations / cryptanalysis, LWE, lattice

Date: received 23 Oct 2015, last revised 26 Oct 2015

Contact author: aono at nict go jp

Available format(s): PDF | BibTeX Citation

Version: 20151027:030217 (All versions of this report)

Short URL: ia.cr/2015/1026

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]