Rigorous and efficient short lattice vectors enumeration

Xavier Pujol, Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

21 Citations (Scopus)

Abstract

The Kannan-Fincke-Pohst enumeration algorithm for the shortest and closest lattice vector problems is the keystone of all strong lattice reduction algorithms and their implementations. In the context of the fast developing lattice-based cryptography, the practical security estimates derive from floating-point implementations of these algorithms. However, these implementations behave very unexpectedly and make these security estimates debatable. Among others, numerical stability issues seem to occur and raise doubts on what is actually computed. We give here the first results on the numerical behavior of the floating-point enumeration algorithm. They provide a theoretical and practical framework for the use of floating-point numbers within strong reduction algorithms, which could lead to more sensible hardness estimates.
Original languageEnglish
Title of host publicationAdvances in cryptology - ASIACRYPT 2008
Subtitle of host publication14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings
EditorsJosef Pieprzyk
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages390-405
Number of pages16
ISBN (Print)9783540892540
DOIs
Publication statusPublished - 2008
EventInternational Conference on the Theory and Application of Cryptology and Information Security (14th : 2008) - Melbourne, Australia
Duration: 7 Dec 200811 Dec 2008

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume5350

Conference

ConferenceInternational Conference on the Theory and Application of Cryptology and Information Security (14th : 2008)
CityMelbourne, Australia
Period7/12/0811/12/08

Keywords

  • lattices
  • SVP
  • lattice cryptanalysis
  • numerical stability

Fingerprint Dive into the research topics of 'Rigorous and efficient short lattice vectors enumeration'. Together they form a unique fingerprint.

Cite this