Paper 2013/602

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

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
LWELattice-based cryptographyFHE
Contact author(s)
robert fitzpatrick 2010 @ live rhul ac uk
2013-09-23: revised
2013-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Robert Fitzpatrick and Florian G ̈opfert},
      title = {On the Efficacy of Solving LWE by Reduction to Unique-SVP},
      howpublished = {Cryptology ePrint Archive, Paper 2013/602},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.