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