Paper 2012/636

On the Complexity of the BKW Algorithm on LWE

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

Abstract

This work presents a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes. Rather surprisingly, it appears that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension n ≈ 250 when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples.

Note: Final version - accepted to Designs, Codes and Cryptography. Mainly stylistic revisions.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
BKWLWELattice-based Cryptography
Contact author(s)
robert fitzpatrick 2010 @ live rhul ac uk
History
2013-07-12: last of 2 revisions
2012-11-11: received
See all versions
Short URL
https://ia.cr/2012/636
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/636,
      author = {Martin R.  Albrecht and Carlos Cid and Jean-Charles Faugère and Robert Fitzpatrick and Ludovic Perret},
      title = {On the Complexity of the BKW Algorithm on LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2012/636},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/636}},
      url = {https://eprint.iacr.org/2012/636}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.