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.
Type de document :
Communication dans un congrès
SCC 2012 -- Third international conference on Symbolic Computation and Cryptography, Jul 2012, Castro Urdiales, Spain. pp.100-107, 〈http://wmc2012.unican.es/SCC_WMC_2012.pdf〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00776069
Contributeur : Ludovic Perret <>
Soumis le : mardi 16 juillet 2013 - 22:31:34
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mercredi 5 avril 2017 - 13:03:06

Fichier

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

Identifiants

  • HAL Id : hal-00776069, version 2

Collections

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, 〈http://wmc2012.unican.es/SCC_WMC_2012.pdf〉. 〈hal-00776069v2〉

Partager

Métriques

Consultations de la notice

4854

Téléchargements de fichiers

229