On the complexity of the BKW algorithm on LWE

Martin Albrecht 1 Carlos Cid 1 Jean-Charles Faugère 2 Robert Fitzpatrick 1 Ludovic Perret 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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.
Type de document :
Article dans une revue
Designs, Codes and Cryptography, Springer Verlag, 2015, 74 (2), pp.26. <10.1007/s10623-013-9864-x>
Liste complète des métadonnées

https://hal.inria.fr/hal-00921517
Contributeur : Ludovic Perret <>
Soumis le : lundi 6 janvier 2014 - 12:19:53
Dernière modification le : vendredi 27 novembre 2015 - 10:57:02
Document(s) archivé(s) le : jeudi 10 avril 2014 - 15:40:22

Fichier

636.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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>

Partager

Métriques

Consultations de
la notice

278

Téléchargements du document

220