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.
Original language | English |
---|---|
Title of host publication | Information Security and Cryptology - ICISC 2013. Revised Selected Papers |
Publisher | Springer |
Publication date | 2014 |
Pages | 293–310 |
ISBN (Print) | 978-3-319-12159-8 |
ISBN (Electronic) | 978-3-319-12160-4 |
DOIs | |
Publication status | Published - 2014 |
Event | 16th Annual International Conference on Information Security and Cryptology - Konkuk University, Seoul, Korea, Republic of Duration: 27 Nov 2013 → 29 Nov 2013 Conference number: 16 http://www.icisc.org/icisc13/asp/01.html |
Conference
Conference | 16th Annual International Conference on Information Security and Cryptology |
---|---|
Number | 16 |
Location | Konkuk University |
Country/Territory | Korea, Republic of |
City | Seoul |
Period | 27/11/2013 → 29/11/2013 |
Internet address |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 8565 |
ISSN | 0302-9743 |