Book chapter · Conference paper
On the Efficacy of Solving LWE by Reduction to Unique-SVP
In
Lecture Notes in Computer Science
—
2014, pp. 293-310
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.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2014 |
| Pages: | 293-310 |
| Proceedings: | 16th Annual International Conference on Information Security and CryptologyInternational Conference on Information Security and Cryptology |
| Series: | Lecture Notes in Computer Science |
| ISBN: | 3319121596 , 331912160X , 331912160x , 9783319121598 and 9783319121604 |
| ISSN: | 16113349 and 03029743 |
| Types: | Book chapter and Conference paper |
| DOI: | 10.1007/978-3-319-12160-4_18 |
