Rigorous and efficient short lattice vectors enumeration

Xavier Pujol; Damien Stehlé

doi:10.1007/978-3-540-89255-7_24

Rigorous and efficient short lattice vectors enumeration

Xavier Pujol, Damien Stehlé

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

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 language	English
Title of host publication	Advances in cryptology - ASIACRYPT 2008
Subtitle of host publication	14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings
Editors	Josef Pieprzyk
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	390-405
Number of pages	16
ISBN (Print)	9783540892540
DOIs	https://doi.org/10.1007/978-3-540-89255-7_24
Publication status	Published - 2008
Event	International Conference on the Theory and Application of Cryptology and Information Security (14th : 2008) - Melbourne, Australia Duration: 7 Dec 2008 → 11 Dec 2008

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	5350

Conference

Conference	International Conference on the Theory and Application of Cryptology and Information Security (14th : 2008)
City	Melbourne, Australia
Period	7/12/08 → 11/12/08

Keywords

lattices
SVP
lattice cryptanalysis
numerical stability

Access to Document

10.1007/978-3-540-89255-7_24

Cite this

Pujol, X., & Stehlé, D. (2008). Rigorous and efficient short lattice vectors enumeration. In J. Pieprzyk (Ed.), Advances in cryptology - ASIACRYPT 2008: 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings (pp. 390-405). (Lecture notes in computer science; Vol. 5350). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-89255-7_24

Pujol, Xavier ; Stehlé, Damien. / Rigorous and efficient short lattice vectors enumeration. Advances in cryptology - ASIACRYPT 2008: 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings. editor / Josef Pieprzyk. Berlin : Springer, Springer Nature, 2008. pp. 390-405 (Lecture notes in computer science).

@inproceedings{e03c09eb651846d1a41482899882bb0f,

title = "Rigorous and efficient short lattice vectors enumeration",

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.",

keywords = "lattices, SVP, lattice cryptanalysis, numerical stability",

author = "Xavier Pujol and Damien Stehl{\'e}",

year = "2008",

doi = "10.1007/978-3-540-89255-7_24",

language = "English",

isbn = "9783540892540",

series = "Lecture notes in computer science",

publisher = "Springer, Springer Nature",

pages = "390--405",

editor = "Josef Pieprzyk",

booktitle = "Advances in cryptology - ASIACRYPT 2008",

address = "United States",

note = "International Conference on the Theory and Application of Cryptology and Information Security (14th : 2008) ; Conference date: 07-12-2008 Through 11-12-2008",

}

Pujol, X & Stehlé, D 2008, Rigorous and efficient short lattice vectors enumeration. in J Pieprzyk (ed.), Advances in cryptology - ASIACRYPT 2008: 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings. Lecture notes in computer science, vol. 5350, Springer, Springer Nature, Berlin, pp. 390-405, International Conference on the Theory and Application of Cryptology and Information Security (14th : 2008), Melbourne, Australia, 7/12/08. https://doi.org/10.1007/978-3-540-89255-7_24

Rigorous and efficient short lattice vectors enumeration. / Pujol, Xavier; Stehlé, Damien.
Advances in cryptology - ASIACRYPT 2008: 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings. ed. / Josef Pieprzyk. Berlin: Springer, Springer Nature, 2008. p. 390-405 (Lecture notes in computer science; Vol. 5350).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Rigorous and efficient short lattice vectors enumeration

AU - Pujol, Xavier

AU - Stehlé, Damien

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - lattices

KW - SVP

KW - lattice cryptanalysis

KW - numerical stability

U2 - 10.1007/978-3-540-89255-7_24

DO - 10.1007/978-3-540-89255-7_24

M3 - Conference proceeding contribution

SN - 9783540892540

T3 - Lecture notes in computer science

SP - 390

EP - 405

BT - Advances in cryptology - ASIACRYPT 2008

A2 - Pieprzyk, Josef

PB - Springer, Springer Nature

CY - Berlin

T2 - International Conference on the Theory and Application of Cryptology and Information Security (14th : 2008)

Y2 - 7 December 2008 through 11 December 2008

ER -

Pujol X, Stehlé D. Rigorous and efficient short lattice vectors enumeration. In Pieprzyk J, editor, Advances in cryptology - ASIACRYPT 2008: 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008 proceedings. Berlin: Springer, Springer Nature. 2008. p. 390-405. (Lecture notes in computer science). doi: 10.1007/978-3-540-89255-7_24

Rigorous and efficient short lattice vectors enumeration

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this