Paper 2010/097

Parallel Enumeration of Shortest Lattice Vectors

Özgür Dagdelen and Michael Schneider

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
shortest vector problemparallelizationenumeration
Contact author(s)
mischnei @ cdc informatik tu-darmstadt de
History
2010-08-23: last of 2 revisions
2010-03-01: received
See all versions
Short URL
https://ia.cr/2010/097
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/097,
      author = {Özgür Dagdelen and Michael Schneider},
      title = {Parallel Enumeration of Shortest Lattice Vectors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/097},
      year = {2010},
      url = {https://eprint.iacr.org/2010/097}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.