Coded-BKW: Solving LWE Using Lattice Codes.

Summary, in English

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}∗.

• Author: Qian Guo; Thomas Johansson; Paul Stankovski
• Editor: Rosario Gennaro; Matthew Robshaw
• Department/s: Department of Electrical and Information Technology; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publishing year: 2015
• Language: English
• Pages: 23-42
• Publication/Series: Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science
• Volume: 9215
• Links: http://dx.doi.org/10.1007/978-3-662-47989-6_2
• Document type: Conference paper
• Publisher: Springer
• Topic: Communication Systems
• Conference name: 35th Annual Cryptology Conference
• Conference date: 2015-08-16 - 2015-08-20
• Status: Published
• Research group: Crypto and Security
• ISBN/ISSN/Other: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-662-47988-9