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

Martin Roland Albrecht; Robert Fitzpatrick; Florian  Göpfert

doi:10.1007/978-3-319-12160-4_18

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

Martin Roland Albrecht, Robert Fitzpatrick, Florian Göpfert

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 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	https://doi.org/10.1007/978-3-319-12160-4_18
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	http://www.icisc.org/icisc13/asp/01.html

Series	Lecture Notes in Computer Science
Volume	8565
ISSN	0302-9743

Access to Document

10.1007/978-3-319-12160-4_18

OpenUrl availability

Full text

Cite this

@inproceedings{fef11f186cb94b29b10802797d2dc677,

title = "On the Efficacy of Solving LWE by Reduction to Unique-SVP",

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 {\textquoteleft}embedding{\textquoteright} 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.",

author = "Albrecht, {Martin Roland} and Robert Fitzpatrick and Florian G{\"o}pfert",

year = "2014",

doi = "10.1007/978-3-319-12160-4_18",

language = "English",

isbn = " 978-3-319-12159-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "293–310",

booktitle = "Information Security and Cryptology - ICISC 2013. Revised Selected Papers",

note = "16th Annual International Conference on Information Security and Cryptology, ICISC 2013 ; Conference date: 27-11-2013 Through 29-11-2013",

url = "http://www.icisc.org/icisc13/asp/01.html",

}

Albrecht, MR, 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. Springer, Lecture Notes in Computer Science, vol. 8565, pp. 293–310, 16th Annual International Conference on Information Security and Cryptology, Seoul, Korea, Republic of, 27/11/2013. https://doi.org/10.1007/978-3-319-12160-4_18

On the Efficacy of Solving LWE by Reduction to Unique-SVP. / Albrecht, Martin Roland; Fitzpatrick, Robert; Göpfert, Florian .
Information Security and Cryptology - ICISC 2013. Revised Selected Papers. Springer, 2014. p. 293–310 (Lecture Notes in Computer Science, Vol. 8565).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

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

AU - Albrecht, Martin Roland

AU - Fitzpatrick, Robert

AU - Göpfert, Florian

N1 - Conference code: 16

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-12160-4_18

DO - 10.1007/978-3-319-12160-4_18

M3 - Article in proceedings

SN - 978-3-319-12159-8

T3 - Lecture Notes in Computer Science

SP - 293

EP - 310

BT - Information Security and Cryptology - ICISC 2013. Revised Selected Papers

PB - Springer

T2 - 16th Annual International Conference on Information Security and Cryptology

Y2 - 27 November 2013 through 29 November 2013

ER -

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

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this