Cryptology ePrint Archive: Report 2016/310
Coded-BKW: Solving LWE Using Lattice Codes
Qian Guo and Thomas Johansson and Paul Stankovski
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 secret vector is sampled from $(0,1)^*$.
Category / Keywords: foundations / LWE; binary-LWE; BKW; Coded-BKW; Lattice codes.
Original Publication (in the same form): IACR-CRYPTO-2015
Date: received 18 Mar 2016
Contact author: fywzguoqian at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20160318:092150 (All versions of this report)
Short URL: ia.cr/2016/310
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]