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

被引：35

作者：

Albrecht, Martin R. ^{[1
]}

Fitzpatrick, Robert ^{[2
]}

Goepfert, Florian ^{[3
]}

机构：

[1] Tech Univ Denmark, DK-2800 Lyngby, Denmark

[2] Univ London, Royal Holloway, ISG, Egham, Surrey, England

[3] Tech Univ Darmstadt, CASED, Darmstadt, Germany

来源：

INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2013 | 2014年 / 8565卷

关键词：

LATTICES;

D O I：

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

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：293 / 310

页数：18

共 22 条

[1]

Albrecht MR, 2011, LECT NOTES COMPUT SC, V7073, P179, DOI 10.1007/978-3-642-25385-0_10

[2]

[Anonymous], STOC 2013 IN PRESS

[3]

[Anonymous], 2009, Post quantum cryptography

[4]

[Anonymous], 1986, CBMS NSF REGIONAL C

[5]

[Anonymous], 2013, GENERATOR LWE RING L

[6]

[Anonymous], DES CODES CRYPTOGR

[7]

[Anonymous], 2011, Paper 2011/139

[8]

Arora S, 2011, LECT NOTES COMPUT SC, V6755, P403, DOI 10.1007/978-3-642-22006-7_34

[9] NEW BOUNDS IN SOME TRANSFERENCE THEOREMS IN THE GEOMETRY OF NUMBERS [J].

BANASZCZYK, W .

MATHEMATISCHE ANNALEN, 1993, 296 (04) :625-635

[10] Efficient Fully Homomorphic Encryption from (Standard) LWE [J].

Brakerski, Zvika ;

Vaikuntanathan, Vinod .

2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :97-106

← 1 2 3 →