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

Martin Roland Albrecht, Robert Fitzpatrick, Florian Göpfert

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2013. Revised Selected Papers
PublisherSpringer
Publication date2014
Pages293–310
ISBN (Print) 978-3-319-12159-8
ISBN (Electronic)978-3-319-12160-4
DOIs
Publication statusPublished - 2014
Event16th Annual International Conference on Information Security and Cryptology - Konkuk University, Seoul, Korea, Republic of
Duration: 27 Nov 201329 Nov 2013
Conference number: 16
http://www.icisc.org/icisc13/asp/01.html

Conference

Conference16th Annual International Conference on Information Security and Cryptology
Number16
LocationKonkuk University
CountryKorea, Republic of
CitySeoul
Period27/11/201329/11/2013
Internet address
SeriesLecture Notes in Computer Science
Volume8565
ISSN0302-9743

Cite this

Albrecht, M. R., Fitzpatrick, R., & Göpfert, F. (2014). On the Efficacy of Solving LWE by Reduction to Unique-SVP. In Information Security and Cryptology - ICISC 2013. Revised Selected Papers (pp. 293–310). Springer. Lecture Notes in Computer Science, Vol.. 8565 https://doi.org/10.1007/978-3-319-12160-4_18