Lazy Modulus Switching for the BKW Algorithm on LWE

Martin Albrecht 1 Jean-Charles Faugère 2 Robert Fitzpatrick 3 Ludovic Perret 2
1 DTU - Technical University of Denmark [Lyngby]
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 RHUL - Royal Holloway [University of London]
Abstract : Some recent constructions based on LWE do not sample the secret uniformly at random but rather from some distribution which produces small entries. The most prominent of these is the binary-LWE problem where the secret vector is sampled from $\{0,1\}^{\ast}$ or $\{-1,0,1\}^{\ast}$. We present a variant of the BKW algorithm for binary-LWE and other small secret variants and show that this variant reduces the complexity for solving binary-LWE. We also give estimates for the cost of solving binary-LWE instances in this setting and demonstrate the advantage of this BKW variant over standard BKW and lattice reduction techniques applied to the SIS problem. Our variant can be seen as a combination of the BKW algorithm with a lazy variant of modulus switching which might be of independent interest.
Type de document :
Communication dans un congrès
Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-00925187
Contributeur : Ludovic Perret <>
Soumis le : mardi 7 janvier 2014 - 16:33:37
Dernière modification le : lundi 29 mai 2017 - 14:21:48
Document(s) archivé(s) le : lundi 7 avril 2014 - 23:55:23

Fichier

bkw-small-secret.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00925187, version 1

Collections

INRIA | UPMC | LIP6

Citation

Martin Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret. Lazy Modulus Switching for the BKW Algorithm on LWE. Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 2014. <hal-00925187>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

280

Téléchargements du document

322

Contact


archive-ouverte@inria.fr