Advanced

Coded-BKW: Solving LWE Using Lattice Codes.

Guo, Qian LU ; Johansson, Thomas LU and Stankovski, Paul LU (2015) 35th Annual Cryptology Conference In Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science 9215. p.23-42
Abstract
In this paper we propose a new algorithm for solving the

Learning With Errors (LWE) problem based on the steps of the famous

Blum-Kalai-Wasserman (BKW) algorithm. The new idea is to introduce

an additional procedure of mapping subvectors into codewords of a lattice

code, thereby increasing the amount of positions that can be cancelled in

each BKW step. The procedure introduces an additional noise term, but

it is shown that by using a sequence of lattice codes with different rates

the noise can be kept small. Developed theory shows that the new approach

compares favorably to previous methods. It performs particularly

well for the binary-LWE case, i.e., when the... (More)
In this paper we propose a new algorithm for solving the

Learning With Errors (LWE) problem based on the steps of the famous

Blum-Kalai-Wasserman (BKW) algorithm. The new idea is to introduce

an additional procedure of mapping subvectors into codewords of a lattice

code, thereby increasing the amount of positions that can be cancelled in

each BKW step. The procedure introduces an additional noise term, but

it is shown that by using a sequence of lattice codes with different rates

the noise can be kept small. Developed theory shows that the new approach

compares favorably to previous methods. It performs particularly

well for the binary-LWE case, i.e., when the secret vector is sampled

from {0, 1}∗. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science
editor
Gennaro, Rosario; Robshaw, Matthew; and
volume
9215
pages
23 - 42
publisher
Springer
conference name
35th Annual Cryptology Conference
external identifiers
  • wos:000364183000002
  • scopus:84943647318
ISSN
1611-3349
0302-9743
ISBN
978-3-662-47988-9
DOI
10.1007/978-3-662-47989-6_2
language
English
LU publication?
yes
id
176059f2-573c-4b6a-bcd3-c74d3099d5cf (old id 8147684)
date added to LUP
2015-11-02 11:14:04
date last changed
2017-09-10 03:07:10
@inproceedings{176059f2-573c-4b6a-bcd3-c74d3099d5cf,
  abstract     = {In this paper we propose a new algorithm for solving the<br/><br>
Learning With Errors (LWE) problem based on the steps of the famous<br/><br>
Blum-Kalai-Wasserman (BKW) algorithm. The new idea is to introduce<br/><br>
an additional procedure of mapping subvectors into codewords of a lattice<br/><br>
code, thereby increasing the amount of positions that can be cancelled in<br/><br>
each BKW step. The procedure introduces an additional noise term, but<br/><br>
it is shown that by using a sequence of lattice codes with different rates<br/><br>
the noise can be kept small. Developed theory shows that the new approach<br/><br>
compares favorably to previous methods. It performs particularly<br/><br>
well for the binary-LWE case, i.e., when the secret vector is sampled<br/><br>
from {0, 1}∗.},
  author       = {Guo, Qian and Johansson, Thomas and Stankovski, Paul},
  booktitle    = {Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science},
  editor       = {Gennaro, Rosario and Robshaw, Matthew},
  isbn         = {978-3-662-47988-9},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {23--42},
  publisher    = {Springer},
  title        = {Coded-BKW: Solving LWE Using Lattice Codes.},
  url          = {http://dx.doi.org/10.1007/978-3-662-47989-6_2},
  volume       = {9215},
  year         = {2015},
}