ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Rigorous and Efficient Short Lattice Vectors Enumeration

Speaker: Damien Stehlé
Date, Time: Fri, 17 Oct 2008 15:00

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 unexpectedly and make these security estimates debatable. Among others, numerical stability issues seem to occur and raise doubts on what is actually computed.

In this talk, after giving some background information on lattices and lattice-based cryptography, I will motivate the need to study the numerical stability of lattice algorithms in the context of the cryptanalysis of lattice-based cryptosystems. I will then describe 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.

Back to the top of this page