Lattice enumeration using extreme pruning

Nicolas Gama; Phong Q. Nguyen; Oded Regev

doi:10.1007/978-3-642-13190-5_13

Lattice enumeration using extreme pruning

Nicolas Gama, Phong Q. Nguyen, Oded Regev

Computer Science

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

Abstract

Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.

Original language	English (US)
Title of host publication	Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages	257-278
Number of pages	22
DOIs	https://doi.org/10.1007/978-3-642-13190-5_13
State	Published - 2010
Event	29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010 - French Riviera, France Duration: May 30 2010 → Jun 3 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6110 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010
Country/Territory	France
City	French Riviera
Period	5/30/10 → 6/3/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-13190-5_13

Cite this

Gama, N., Nguyen, P. Q., & Regev, O. (2010). Lattice enumeration using extreme pruning. In Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 257-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6110 LNCS). https://doi.org/10.1007/978-3-642-13190-5_13

Lattice enumeration using extreme pruning. / Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded.
Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. 2010. p. 257-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6110 LNCS).

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

Gama, N, Nguyen, PQ & Regev, O 2010, Lattice enumeration using extreme pruning. in Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6110 LNCS, pp. 257-278, 29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010, French Riviera, France, 5/30/10. https://doi.org/10.1007/978-3-642-13190-5_13

Gama N, Nguyen PQ, Regev O. Lattice enumeration using extreme pruning. In Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. 2010. p. 257-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13190-5_13

Gama, Nicolas ; Nguyen, Phong Q. ; Regev, Oded. / Lattice enumeration using extreme pruning. Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. 2010. pp. 257-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{be23777ae8504413897af2777c4e0159,

title = "Lattice enumeration using extreme pruning",

abstract = "Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.",

author = "Nicolas Gama and Nguyen, {Phong Q.} and Oded Regev",

year = "2010",

doi = "10.1007/978-3-642-13190-5_13",

language = "English (US)",

isbn = "3642131891",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "257--278",

booktitle = "Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

note = "29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010 ; Conference date: 30-05-2010 Through 03-06-2010",

}

TY - GEN

T1 - Lattice enumeration using extreme pruning

AU - Gama, Nicolas

AU - Nguyen, Phong Q.

AU - Regev, Oded

PY - 2010

Y1 - 2010

N2 - Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.

AB - Lattice enumeration algorithms are the most basic algorithms for solving hard lattice problems such as the shortest vector problem and the closest vector problem, and are often used in public-key cryptanalysis either as standalone algorithms, or as subroutines in lattice reduction algorithms. Here we revisit these fundamental algorithms and show that surprising exponential speedups can be achieved both in theory and in practice by using a new technique, which we call extreme pruning. We also provide what is arguably the first sound analysis of pruning, which was introduced in the 1990s by Schnorr et al.

UR - http://www.scopus.com/inward/record.url?scp=77954651254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954651254&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13190-5_13

DO - 10.1007/978-3-642-13190-5_13

M3 - Conference contribution

AN - SCOPUS:77954651254

SN - 3642131891

SN - 9783642131899

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 257

EP - 278

BT - Advances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

T2 - 29th in the Series of EuropeanConferences on the Theory and Application of Cryptographic Techniques, Eurocrypt 2010

Y2 - 30 May 2010 through 3 June 2010

ER -

Lattice enumeration using extreme pruning

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this