Paper 2010/386

BoostReduce - A Framework For Strong Lattice Basis Reduction

Werner Backes and Susanne Wetzel

Abstract

In this paper, we propose a new generic reduction framework BoostReduce for strong lattice basis reduction. At the core of our new framework is an iterative method which uses a newly-developed algorithm for finding short lattice vectors and integrating them efficiently into an improved lattice basis. We present BoostBKZ as an instance of BoostReduce using the Block-Korkine-Zolotarev (BKZ) reduction. BoostBKZ is tailored to make effective use of modern computer architectures in that it takes advantage of multiple threads. Experimental results of BoostBKZ show a significant reduction in running time while maintaining the quality of the reduced lattice basis in comparison to the traditional BKZ reduction algorithm.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Unknown where it was published
Keywords
lattice techniquesparallel algorithmlattice basis reductionframeworkmulti-corecryptanalysis
Contact author(s)
wbackes @ stevens edu
History
2010-07-07: received
Short URL
https://ia.cr/2010/386
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/386,
      author = {Werner Backes and Susanne Wetzel},
      title = {BoostReduce - A Framework For Strong Lattice Basis Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2010/386},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/386}},
      url = {https://eprint.iacr.org/2010/386}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.