International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Parallel Enumeration of Shortest Lattice Vectors

Authors:
Özgür Dagdelen
Michael Schneider
Download:
URL: http://eprint.iacr.org/2010/097
Search ePrint
Search Google
Abstract: Lattice basis reduction is the problem of finding short vectors in lattices. The security of lattice based cryptosystems is based on the hardness of lattice reduction. Furthermore, lattice reduction is used to attack well-known cryptosystems like RSA. One of the algorithms used in lattice reduction is the enumeration algorithm (ENUM), that provably finds a shortest vector of a lattice. We present a parallel version of the lattice enumeration algorithm. Using multi-core CPU systems with up to 16 cores, our implementation gains a speed-up of up to factor 14. Compared to the currently best public implementation, our parallel algorithm saves more than 90% of runtime.
BibTeX
@misc{eprint-2010-22998,
  title={Parallel Enumeration of Shortest Lattice Vectors},
  booktitle={IACR Eprint archive},
  keywords={implementation / shortest vector problem, parallelization, enumeration},
  url={http://eprint.iacr.org/2010/097},
  note={ mischnei@cdc.informatik.tu-darmstadt.de 14844 received 22 Feb 2010, last revised 23 Aug 2010},
  author={Özgür Dagdelen and Michael Schneider},
  year=2010
}