Cryptology ePrint Archive: Report 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.

Category / Keywords: shortest vector problem, sieving algorithms, ideal lattices

Date: received 22 Aug 2011, last revised 8 Feb 2013

Contact author: mischnei at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20130208:154718 (All versions of this report)

Short URL: ia.cr/2011/458