HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On the complexity of the BKW algorithm on LWE

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 re ned estimates for the data and computational e ort requirements for solving concrete instances of the LWE problem. We apply this re ned 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00921517
Contributor : Ludovic Perret Connect in order to contact the contributor
Submitted on : Monday, January 6, 2014 - 12:19:53 PM
Last modification on : Friday, January 21, 2022 - 3:21:16 AM
Long-term archiving on: : Thursday, April 10, 2014 - 3:40:22 PM

File

636.pdf
Files produced by the author(s)

Identifiers

Citation

Martin Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret. On the complexity of the BKW algorithm on LWE. Designs, Codes and Cryptography, Springer Verlag, 2015, 74 (2), pp.26. ⟨10.1007/s10623-013-9864-x⟩. ⟨hal-00921517⟩

Share

Metrics

Record views

6515

Files downloads

788