Sieving for Shortest Vectors in Ideal Lattices

Michael Schneider

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 problem sieving algorithms ideal 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: 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}
}