Cryptology ePrint Archive: Report 2017/815

Revisiting the Expected Cost of Solving uSVP and Applications to LWE

Martin R. Albrecht and Florian Göpfert and 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.

Category / Keywords: public-key cryptography / cryptanalysis, lattice-based cryptography, learning with errors, lattice reduction

Original Publication (with minor differences): IACR-ASIACRYPT-2017

Date: received 28 Aug 2017, last revised 26 Sep 2017

Contact author: fernando virdia 2016 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Note: Typos, inexact heading in Table 4.

Version: 20170926:150601 (All versions of this report)

Short URL: ia.cr/2017/815

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]