Coded-BKW with Sieving: An Improved Algorithm for Solving the LWE Problem

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the BKW algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For Regev parameters q = n^2 and noise level \sigma = n^1.5/(\sqrt{2\pi} \log_2^2 n), the asymptotic complexity is 2^{0.895n} in the standard setting, improving on the previously best known complexity of roughly 2^{0.930n}. Also for concrete parameter instances, improved performance is indicated.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Other Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving
Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
PublisherSpringer Verlag
Pages323-346
ISBN (Electronic)978-3-319-70694-8
ISBN (Print)978-3-319-70693-1
StatePublished - 2017
Peer-reviewedYes
Event23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017 - Hong Kong, China
Duration: 2017 Dec 32017 Dec 7
Conference number: 23
https://asiacrypt.iacr.org/2017/index.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10624
ISSN (Print)0302-9743

Conference

Conference23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017
Abbreviated titleASIACRYPT
CountryChina
CityHong Kong
Period2017/12/032017/12/07
Internet address