Lattice Sieving and Combinatorial Algorithms

Sieve algorithms are a class of randomized exponential time algorithms for the exact (or almost exact) solution of lattice problems. They improve the asymptotic running time of traditional enumeration algorithms, reducing the dependency of the running time on the lattice dimension from nO(n)n^{O(n)} to single exponential 2cn2^{c n} for some constant c=O(1)c=O(1). The improvement is achieved at the cost of introducing randomization and using exponential space. Sieve algorithms have been studied primarily as a method to find exact solutions to the shortest vector problem (SVP) in the euclidean norm, but they can be adapted to other norms and other lattice problems.

There are two main types of lattice sieve algorithms:

Somehow related to sieving, is a newer type of combinatorial algorithms which work by building a list of short random vectors (not necessarily in the lattice), and then try to produce short lattice vectors by taking linear combinations of the vectors in the list.

Current provable versions of lattice sieve algorithms (as well as combinatorial ones) are not particularly effective, due both to their high exponential space complexity, and other inefficiencies associated to the use of random perturbations. However, they are the basis of several heuristic variants that have been implemented and shown to offer an interesting alternative to traditional enumeration methods.

SODA 2010: slides See slides from presentation of (2) for an illustration of how sieve algorithms work, the impact of random perturbations on performance of provable algorithms, and some performance data on practical implementations.

Provable Sieve Algorithms

The first sieve algorithm for lattice problems was proposed in

  1. A sieve algorithm for the shortest lattice vector problem
    (Ajtai, Kumar & Sivakumar - STOC 2001)

which provably solves SVP in the Euclidean norm. It holds a special place in the historical development of lattice algorithms as the first method to solve a hard lattice problem in single exponential time 2O(n)2^{O(n)}. The constant cc in the exponent of the running time 2cn2^{cn} was initially rather large, but it has been improved in

  1. Faster exponential time algorithms for the shortest vector problem
    (Micciancio & Voulgaris - SODA 2010) [eccc, slides, code]

  2. Algorithms for the shortest and closest lattice vector problems
    (Hanrot, Pujol & Stehle - IWCC 2011) [pdf] (See also ePrint 2009/605)

first to c3.199c\approx 3.199 (2) and then to c2.465c\approx 2.465 (3). Combinatorial algorithms further improve this constant to c1c\approx 1.

Heuristic Sieve Algorithms

Provable versions of sieve algorithms make use of random perturbations which greatly affect their performance. Heuristic variants of sieve algorithms avoid the use of perturbations, and while losing provable correctness and running time guarantees, they perform much better in practice. The first heuristic variant of sieve algorithms was proposed in

  1. Sieve algorithms for the shortest vector problem are practical
    (Nguyen & Vidick - J. Math. Crypt. 2(2) 2008) [pdf]

which demonstrated that this type of algorithms can be run in practice in moderately low dimension, though still not competitive with enumeration techniques. A much faster heuristic algorithm (the Gauss Sieve) was then proposed in (2), which has been the target of many implementations and experimental studies. Many other heuristic sieve algorithms have been subsequently proposed, improving (4) and (2) using various forms of hashing.

  1. Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem
    (Wang, Liu, Tian & Bi - AsiaCCS 2011) [ePrint]

  2. A three-level sieve algorithm for the shortest vector problem
    (Zhang, Pan & Hu - SAC 2013) [ePrint, slides]

  3. Sieving for shortest vectors in lattices using angular locality-sensitive hashing
    (Laarhoven - Crypto 2015) [ePrint]

  4. Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
    (Laarhoven & de Weger - LatinCrypt 2015) [ePrint]

  5. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search
    (Becker, Gama & Joux - ePrint 2015/522)

  6. Efficient (ideal) lattice sieving using cross-polytope LSH
    (Becker & Laarhoven - ePrint 2015/823)

The paper (8) heuristically achieves the constant c0.297c \approx 0.297 in the exponent of the running time, but the algorithm is not entirely practical.

Other norms and lattice problems

Lattice sieve algorithms can be generalized to solve problems other than SVP (albeit only approximately, within a factor 1+ϵ1+\epsilon), and work in arbitrary norms.

  1. Sampling short lattice vectors and the closest lattice vector problem
    (Ajtai, Kumar & Sivakumar - CCC 2002)
    approximates CVP (in the Euclidean norm) within a factor 1+ϵ1+\epsilon in time 2O(n/ϵ)2^{O(n/\epsilon)}.

  2. Sampling methods for shortest vectors, closest vectors and successive minima
    (Blömer & Naewe - TCS 410(18) 2009 / ICALP 2007)
    improves the dependency of the running time on ε to (1/ε)O(n)(1/ε)^{O(n)}, and extends the algorithm to any LpL_p norm

  3. Covering cubes and the closest vector problem
    (Eisenbrand, Hahnle & Nieneier - SoCG 2011) [arXiv]
    further improves dependency on ϵ\epsilon to (log(1/ε))O(n)(\log (1/ε))^{O(n)} for approximate CVP in the LL_\infty norm

  4. Some sieving algorithms for lattice problems
    (Arvind & Joglekar - FSTTCS 2008)
    further extends the SVP algorithm to arbitrary (not necessarily LpL_p) norms

  5. A randomized sieving algorithm for approximate integer programming
    (Dadush - Algorithmica 70(2), 2014 / Latin 2012)
    extends sieve algorithms to solve approximate integer programming


Implementations and experimental evaluations of the Gauss Sieve and other algorithms are described in

  1. Analysis of Gauss-sieve for solving the shortest vector problem in lattices
    (Schneider - WALCOM 2011)

  2. A parallel implementation of GaussSieve for the shortest vector problem in lattices
    (Milde & Schneider - PaCT 2011)

  3. Sieving for shortest vectors in ideal lattices
    (Schneider - AfricaCrypt 2013) [ePrint]

  4. Parallel Gauss sieve algorithm: solving the SVP challenge over a 128-dimensional ideal lattice
    (Ishiguro, Kiyomoto, Miyake & Takagi - PKC 2014) [ePrint]

  5. Tuning GaussSieve for speed
    (Fitzpatrick, Bischof, Buchmann, Dagdelen, Gopfert, Mariano & Yang - LatinCrypt 2014) [ePrint]

  6. A comprehensive empirical comparison of (parallel) ListSieve and GaussSieve
    (Mariano, Dagdelen, Bischof - APCI&E 2014) [ePrint]

  7. Lock-free GaussSieve for linear speedups in parallel high performance SVP calculation
    (Mariano, Timnat, Bischof - SBAC-PAR 2014) [ePrint]

  8. Parallel (probable) lock-free HashSieve: a practical sieving algorithm for the SVP
    (Mariano, Laarhoven & Bischof - ICPP 2015) [ePrint]

Combinatorial Algorithms

Somehow related to sieve algorithms is a class of combinatorial algorithms that work by building a list of random short vectors (not necessarily in the lattice), and then attempting to find a short lattice vector by taking linear combinations of the vectors in the list. The approach is also related to the methods used to establish a connection between the worst-case and average-case complexity of lattice problems. However, its use in the context of algorithmic design is simplified by the fact that the target problem instances do not have to be uniformly random.

A first heuristic algorithm of this kind was proposed in

  1. A sieve algorithm based on overlattices
    (Becker, Gama & Joux - ANTS 2014 / LMS J. Comp. Math.) [ePrint]

The algorithm is practical, but it is only analyzed under heuristic assumptions. A theoretical algorithm using related ideas together with Gaussian sampling techniques is given in

  1. Solving the Shortest Vector Problem in 2n2^n Time via Discrete Gaussian Sampling
    (Aggarwal, Dadush, Regev & Stephens-Davidowitz - STOC 2015) [arXiv]

This algorithm provably solves SVP in time 2n2^n (achieving constant c=1c=1 in the exponent) and it is the currently best theoretical bound on the complexity of SVP. Justs like sieve algorithms, it uses exponential space and randomness. It improves theoretical sieve algorithms by avoiding the use of perturbations, but it also introduces other inefficiencies that make it mostly of theoretical interest.

Open Problems

PhD Theses

  1. Algorithms for the closest and shortest vector problems on general lattices
    (Voulgaris - PhD Thesis, UCSD 2011)

  2. Algorithms for lattice problems with respect to general norms
    (Naewe - PhD Thesis, U. Paderborn 2011)