Paper 2017/815

Revisiting the Expected Cost of Solving uSVP and Applications to LWE

Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer

Abstract

Abstract: Reducing the Learning with Errors problem (LWE) to the Unique-SVP problem and then applying lattice reduction is a commonly relied-upon strategy for estimating the cost of solving LWE-based constructions. In the literature, two different conditions are formulated under which this strategy is successful. One, widely used, going back to Gama & Nguyen's work on predicting lattice reduction (Eurocrypt 2008) and the other recently outlined by Alkim et al. (USENIX 2016). Since these two estimates predict significantly different costs for solving LWE parameter sets from the literature, we revisit the Unique-SVP strategy. We present empirical evidence from lattice-reduction experiments exhibiting a behaviour in line with the latter estimate. However, we also observe that in some situations lattice-reduction behaves somewhat better than expected from Alkim et al.'s work and explain this behaviour under standard assumptions. Finally, we show that the security estimates of some LWE-based constructions from the literature need to be revised and give refined expected solving costs.

Note: Typos, inexact heading in Table 4.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
cryptanalysislattice-based cryptographylearning with errorslattice reduction
Contact author(s)
fernando virdia 2016 @ rhul ac uk
History
2017-09-26: last of 2 revisions
2017-08-31: received
See all versions
Short URL
https://ia.cr/2017/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/815,
      author = {Martin R.  Albrecht and Florian Göpfert and Fernando Virdia and Thomas Wunderer},
      title = {Revisiting the Expected Cost of Solving uSVP and Applications to LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/815},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/815}},
      url = {https://eprint.iacr.org/2017/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.