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

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

Paper 2013/602 Original: eprint.iacr.org/2013/602 ↗

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

Martin R. Albrecht

Robert Fitzpatrick

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2013-09-23: last updated; 2013-09-19: published
Short URL: https://ia.cr/2013/602
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2013/602,
      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},
      url = {https://eprint.iacr.org/2013/602}
}