Skip to Main content Skip to Navigation
Conference papers

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 refined estimates forthe 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00776069
Contributor : Ludovic Perret <>
Submitted on : Tuesday, July 16, 2013 - 10:31:34 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 1:03:06 PM

File

final_BKW.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00776069, version 2

Citation

Martin Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret. On the Complexity of the BKW Algorithm on LWE. SCC 2012 -- Third international conference on Symbolic Computation and Cryptography, Jul 2012, Castro Urdiales, Spain. pp.100-107. ⟨hal-00776069v2⟩

Share

Metrics

Record views

6686

Files downloads

561