Lazy Modulus Switching for the BKW Algorithm on LWE

Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret

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}&#8727; or {&#8722;1, 0, 1}&#8727;. 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in PKC 2014
Keywords
Learning with Errors
Contact author(s)
History
Short URL
https://ia.cr/2014/019

CC BY

BibTeX

@misc{cryptoeprint:2014/019,
author = {Martin R.  Albrecht and Jean-Charles Faugère and Robert Fitzpatrick and Ludovic Perret},
title = {Lazy Modulus Switching for the BKW Algorithm on LWE},
howpublished = {Cryptology ePrint Archive, Paper 2014/019},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/019}},
url = {https://eprint.iacr.org/2014/019}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.