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
-
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},
url = {https://eprint.iacr.org/2017/815}
}
