Coded-BKW: Solving LWE Using Lattice Codes.

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Kommunikationssystem
Originalspråkengelska
Titel på värdpublikationAdvances in Cryptology -- CRYPTO 2015/Lecture notes in computer science
RedaktörerRosario Gennaro, Matthew Robshaw
FörlagSpringer
Sidor23-42
Volym9215
ISBN (tryckt)978-3-662-47988-9
StatusPublished - 2015
PublikationskategoriForskning
Peer review utfördJa
Evenemang35th Annual Cryptology Conference - Santa Barbara, CA, USA,
Varaktighet: 2015 aug 162015 aug 20

Publikationsserier

Namn
Volym9215
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens35th Annual Cryptology Conference
Period2015/08/162015/08/20

Relaterad forskningsoutput

Qian Guo, 2016, Department of Electrical and Information Technology, Lund University. 243 s.

Forskningsoutput: AvhandlingDoktorsavhandling (sammanläggning)

Visa alla (1)