| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [31 references]
https://hal.inria.fr/hal-00921517
Contributor : Ludovic Perret <>
Submitted on : Monday, January 6, 2014 - 12:19:53 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Thursday, April 10, 2014 - 3:40:22 PM
Contributor : Ludovic Perret <>
Submitted on : Monday, January 6, 2014 - 12:19:53 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Thursday, April 10, 2014 - 3:40:22 PM
File
636.pdf
Files produced by the author(s)