Coded-BKW: Solving LWE Using Lattice Codes.
Författare
Redaktör
- Rosario Gennaro
- Matthew Robshaw
Summary, in English
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}∗.
Avdelning/ar
Publiceringsår
2015
Språk
Engelska
Sidor
23-42
Publikation/Tidskrift/Serie
Advances in Cryptology -- CRYPTO 2015/Lecture notes in computer science
Volym
9215
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Communication Systems
Conference name
35th Annual Cryptology Conference
Conference date
2015-08-16 - 2015-08-20
Status
Published
Forskningsgrupp
- Crypto and Security
ISBN/ISSN/Övrigt
- ISSN: 1611-3349
- ISSN: 0302-9743
- ISBN: 978-3-662-47988-9