Cryptology ePrint Archive: Report 2013/602

On the Efficacy of Solving LWE by Reduction to Unique-SVP

Martin R. Albrecht and Robert Fitzpatrick and Florian G ̈opfert

Abstract: We present a study of the concrete complexity of solving instances of the unique shortest vector problem (uSVP). In particular, we study the complexity of solving the Learning with Errors (LWE) problem by reducing the Bounded-Distance Decoding (BDD) problem to uSVP and attempting to solve such instances using the ‘embedding’ approach. We experimentally derive a model for the success of the approach, compare to alternative methods and demonstrate that for the LWE instances considered in this work, reducing to uSVP and solving via embedding compares favorably to other approaches.

Category / Keywords: LWE, Lattice-based cryptography, FHE

Date: received 17 Sep 2013, last revised 23 Sep 2013

Contact author: robert fitzpatrick 2010 at live rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20130923:182938 (All versions of this report)

Short URL: ia.cr/2013/602

Discussion forum: Show discussion | Start new discussion