A Caltech Library Service

Sieve algorithms for the shortest vector problem are practical

Nguyen, Phong Q. and Vidick, Thomas (2008) Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2 (2). pp. 181-207. ISSN 1862-2976. doi:10.1515/jmc.2008.009.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The most famous lattice problem is the Shortest Vector Problem (SVP), which has many applications in cryptology. The best approximation algorithms known for SVP in high dimension rely on a subroutine for exact SVP in low dimension. In this paper, we assess the practicality of the best (theoretical) algorithm known for exact SVP in low dimension: the sieve algorithm proposed by Ajtai, Kumar and Sivakumar (AKS) in 2001. AKS is a randomized algorithm of time and space complexity 2^(O(n)), which is theoretically much lower than the super-exponential complexity of all alternative SVP algorithms. Surprisingly, no implementation and no practical analysis of AKS has ever been reported. It was in fact widely believed that AKS was impractical: for instance, Schnorr claimed in 2003 that the constant hidden in the 2^(O(n)) complexity was at least 30. In this paper, we show that AKS can actually be made practical: we present a heuristic variant of AKS whose running time is (4/3+ϵ)^n polynomial-time operations, and whose space requirement is (4/3+ ϵ)^(n/2) polynomially many bits. Our implementation can experimentally find shortest lattice vectors up to dimension 50, but is slower than classical alternative SVP algorithms in these dimensions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2008 de Gruyter. Received 4 October, 2007. Published online: 11 Sep 2008.
Subject Keywords:Lattices; AKS Algorithm; sieve; LLL; enumeration
Issue or Number:2
Classification Code:AMS classification: 11Y16, 11H06
Record Number:CaltechAUTHORS:20200804-103250325
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104723
Deposited By: Tony Diaz
Deposited On:04 Aug 2020 19:00
Last Modified:16 Nov 2021 18:34

Repository Staff Only: item control page