Probabilistic Analysis of LLL Reduced Bases

Schneider, Michael

doi:10.4230/DagSemProc.09221.4

Document

Probabilistic Analysis of LLL Reduced Bases

Author Michael Schneider

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 9221
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2009-08-20

PDF

File

PDF

DagSemProc.09221.4.pdf

Filesize: 257 kB
6 pages

Document Identifiers

DOI: 10.4230/DagSemProc.09221.4
URN: urn:nbn:de:0030-drops-21267

Subject Classification

Keywords

Lattice reduction
LLL algorithm

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

LLL reduction, originally founded in 1982 to factor certain polynomials, is a useful tool in public key cryptanalysis. The search for short lattice vectors helps determining the practical hardness of lattice problems, which are supposed to be secure against quantum computer attacks.
It is a fact that in practice, the LLL algorithm finds much shorter vectors than its theoretic analysis guarantees. Therefore one can see that the guaranteed worst case bounds are not helpful for practical purposes. We use a probabilistic approach to give an estimate for the length of the shortest vector in an LLL-reduced bases that is tighter than the worst case bounds.

Cite As Get BibTex

Michael Schneider. Probabilistic Analysis of LLL Reduced Bases. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/DagSemProc.09221.4

Author Details

Michael Schneider

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail