On the Complexity of the BKW Algorithm on LWE

We (with Carlos CidJean-Charles FaugèreRobert Fitzpatrick and Ludovic Perret) have finally managed to put our work on BKW on ePrint.


In this paper we present 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, as a result,  provide new upper bounds for the concrete hardness of these LWE-based schemes.

The source code of our (not very efficient!) implementation of BKW is available on bitbucket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s