Paper 2015/1026

Hardness Estimation of LWE via Band Pruning

Yoshinori Aono, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysisLWElattice
Contact author(s)
aono @ nict go jp
History
2015-10-27: revised
2015-10-26: received
See all versions
Short URL
https://ia.cr/2015/1026
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1026,
      author = {Yoshinori Aono and Le Trieu Phong and Lihua Wang},
      title = {Hardness Estimation of LWE via Band Pruning},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1026},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1026}},
      url = {https://eprint.iacr.org/2015/1026}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.