Paper 2011/458

Sieving for Shortest Vectors in Ideal Lattices

Michael Schneider

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
shortest vector problemsieving algorithmsideal lattices
Contact author(s)
mischnei @ cdc informatik tu-darmstadt de
History
2013-02-08: revised
2011-08-24: received
See all versions
Short URL
https://ia.cr/2011/458
License
Creative Commons Attribution
CC BY

BibTeX

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