Coded-BKW: Solving LWE Using Lattice Codes.
Guo, Qian LU ; Johansson, Thomas LU
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:
https://lup.lub.lu.se/record/8147684
- author
- Guo, Qian
LU
; Johansson, Thomas
LU
and Stankovski, Paul
LU
- organization
- publishing date
- 2015
- 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-04-07 00:06:09
@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}},
}