Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Coded-BKW: Solving LWE Using Lattice Codes.

Guo, Qian LU ; Johansson, Thomas LU orcid and Stankovski, Paul LU (2015) 35th Annual Cryptology Conference 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
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science
editor
Gennaro, Rosario and Robshaw, Matthew
volume
9215
pages
23 - 42
publisher
Springer
conference name
35th Annual Cryptology Conference
conference dates
2015-08-16 - 2015-08-20
external identifiers
  • wos:000364183000002
  • scopus:84943647318
ISSN
0302-9743
1611-3349
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
2016-04-01 10:06:56
date last changed
2024-10-06 20:44:07
@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         = {{0302-9743}},
  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}},
  doi          = {{10.1007/978-3-662-47989-6_2}},
  volume       = {{9215}},
  year         = {{2015}},
}