License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09221.4
URN: urn:nbn:de:0030-drops-21267
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2126/
Go to the corresponding Portal

Schneider, Michael

Probabilistic Analysis of LLL Reduced Bases

pdf-format:
09221.SchneiderMichael.Paper.2126.pdf (0.3 MB)

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.


BibTeX - Entry

@InProceedings{schneider:DagSemProc.09221.4,
  author =	{Schneider, Michael},
  title =	{{Probabilistic Analysis of LLL Reduced Bases}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2126},
  URN =		{urn:nbn:de:0030-drops-21267},
  doi =		{10.4230/DagSemProc.09221.4},
  annote =	{Keywords: Lattice reduction, LLL algorithm}
}

Keywords: Lattice reduction, LLL algorithm
Collection: 09221 - Algorithms and Number Theory
Issue Date: 2009
Date of publication: 20.08.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI