International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

BoostReduce - A Framework For Strong Lattice Basis Reduction

Authors:
Werner Backes
Susanne Wetzel
Download:
URL: http://eprint.iacr.org/2010/386
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23287,
  title={BoostReduce - A Framework For Strong Lattice Basis Reduction},
  booktitle={IACR Eprint archive},
  keywords={applications / lattice techniques, parallel algorithm, lattice basis reduction, framework, multi-core, cryptanalysis},
  url={http://eprint.iacr.org/2010/386},
  note={ wbackes@stevens.edu 14797 received 7 Jul 2010},
  author={Werner Backes and Susanne Wetzel},
  year=2010
}