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

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2017
cryptanalysislattice-based cryptographylearning with errorslattice reduction
Contact author(s)
fernando virdia 2016 @ rhul ac uk
2017-09-26: last of 2 revisions
2017-08-31: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.