Lazy Modulus Switching for the BKW Algorithm on LWE

Martin Roland Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Some recent constructions based on LWE do not sample the secret uniformly at random but rather from some distribution which produces small entries. The most prominent of these is the binary-LWE problem where the secret vector is sampled from {0, 1}* or {−1, 0, 1}*. We present a variant of the BKW algorithm for binary-LWE and other small secret variants and show that this variant reduces the complexity for solving binary-LWE. We also give estimates for the cost of solving binary-LWE instances in this setting and demonstrate the advantage of this BKW variant over standard BKW and lattice reduction techniques applied to the SIS problem. Our variant can be seen as a combination of the BKW algorithm with a lazy variant of modulus switching which might be of independent interest.
Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2014 : Proceedings
PublisherSpringer
Publication date2014
Pages429-445
ISBN (Print)978-3-642-54630-3
ISBN (Electronic)978-3-642-54631-0
DOIs
Publication statusPublished - 2014
Event17th International Conference on Practice and Theory in Public-Key Cryptography - Buenos Aires, Argentina
Duration: 26 Mar 201428 Mar 2014
Conference number: 17

Conference

Conference17th International Conference on Practice and Theory in Public-Key Cryptography
Number17
Country/TerritoryArgentina
CityBuenos Aires
Period26/03/201428/03/2014
SeriesLecture Notes in Computer Science
Volume8383
ISSN0302-9743

Bibliographical note

© International Association for Cryptologic Research 2014

Fingerprint

Dive into the research topics of 'Lazy Modulus Switching for the BKW Algorithm on LWE'. Together they form a unique fingerprint.

Cite this