Paper 2011/458

Sieving for Shortest Vectors in Ideal Lattices

Michael Schneider


Lattice based cryptography is gaining more and more importance in the cryptographic community. It is a common approach to use a special class of lattices, so-called ideal lattices, as the basis of lattice based crypto systems. This speeds up computations and saves storage space for cryptographic keys. The most important underlying hard problem is the shortest vector problem. So far there is no algorithm known that solves the shortest vector problem in ideal lattices faster than in regular lattices. Therefore, crypto systems using ideal lattices are considered to be as secure as their regular counterparts. In this paper we present IdealListSieve, a variant of the ListSieve algorithm, that is a randomized, exponential time sieving algorithm solving the shortest vector problem in lattices. Our variant makes use of the special structure of ideal lattices. We show that it is indeed possible to find a shortest vector in ideal lattices faster than in regular lattices without special structure. The practical speedup of our algorithm is linear in the degree of the field polynomial. We also propose an ideal lattice variant of the heuristic GaussSieve algorithm that allows for the same speedup.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
shortest vector problemsieving algorithmsideal lattices
Contact author(s)
mischnei @ cdc informatik tu-darmstadt de
2013-02-08: revised
2011-08-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Schneider},
      title = {Sieving for Shortest Vectors in Ideal Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2011/458},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.