Paper 2016/004

Bounding basis reduction properties

Arnold Neumaier

Abstract

The paper describes improved analysis techniques for basis reduction that allow one to prove strong complexity bounds and reduced basis guarantees for traditional reduction algorithms and some of their variants. This is achieved by a careful exploitation of the linear equations and inequalities relating various bit sizes before and after one or more reduction steps.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
basis reductionlatticesBKZ algorithmLLL algorithm
Contact author(s)
Arnold Neumaier @ univie ac at
History
2016-01-05: revised
2016-01-04: received
See all versions
Short URL
https://ia.cr/2016/004
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/004,
      author = {Arnold Neumaier},
      title = {Bounding basis reduction properties},
      howpublished = {Cryptology ePrint Archive, Paper 2016/004},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/004}},
      url = {https://eprint.iacr.org/2016/004}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.