On the efficacy of solving LWE by reduction to unique-SVP. (English) Zbl 1368.94082

Lee, Hyang-Sook (ed.) et al., Information security and cryptology – ICISC 2013. 16th international conference, Seoul, Korea, November 27–29, 2013. Revised selected papers. Cham: Springer (ISBN 978-3-319-12159-8/pbk; 978-3-319-12160-4/ebook). Lecture Notes in Computer Science 8565, 293-310 (2014).
Summary: 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.
For the entire collection see [Zbl 1318.68030].


94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI Link