Cryptology ePrint Archive: Report 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.

Category / Keywords: basis reduction; lattices; BKZ algorithm; LLL algorithm

Date: received 3 Jan 2016, last revised 5 Jan 2016

Contact author: Arnold Neumaier at univie ac at

Available format(s): PDF | BibTeX Citation

Version: 20160105:162803 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]