Cryptology ePrint Archive: Report 2012/636

On the Complexity of the BKW Algorithm on LWE

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

Abstract: This work presents a study of the complexity of the Blum-Kalai-Wasserman (BKW) algo- rithm 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.

Category / Keywords: foundations / learning with errors, algorithm

Date: received 8 Nov 2012, last revised 7 May 2013

Contact author: robert fitzpatrick 2010 at live rhul ac uk

Available formats: PDF | BibTeX Citation

Version: 20130507:205608 (All versions of this report)

Discussion forum: Show discussion | Start new discussion