Generating Shorter Bases for Hard Random Lattices

Abstract : We revisit the problem of generating a “hard” random lattice together with a basis of relatively short vectors. This problem has gained in importance lately due to new cryptographic schemes that use such a procedure for generating public/secret key pairs. In these applications, a shorter basis directly corresponds to milder underlying complexity assumptions and smaller key sizes. The contributions of this work are twofold. First, using the Hermite normal form as an organizing principle, we simplify and generalize an approach due to Ajtai (ICALP 1999). Second, we improve the construction and its analysis in several ways, most notably by tightening the length of the output basis essentially to the optimum value.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.75-86, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00359718
Contributeur : Publications Loria <>
Soumis le : lundi 9 février 2009 - 11:37:22
Dernière modification le : mercredi 29 novembre 2017 - 10:27:41
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:31:14

Fichier

06-alwen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359718, version 1

Collections

Citation

Joël Alwen, Chris Peikert. Generating Shorter Bases for Hard Random Lattices. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.75-86, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359718〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

328