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 $2^{O(n)}$. The constant $c$ in the exponent of the running time $2^{cn}$ was initially rather large, but it has been improved in

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

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

first to $c\approx 3.199$ (2) and then to $c\approx 2.465$ (3). Combinatorial algorithms further improve this constant to $c\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

4. 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.

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

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

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

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

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

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

The paper (8) heuristically achieves the constant $c \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+\epsilon$), and work in arbitrary norms.

11. 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+\epsilon$ in time $2^{O(n/\epsilon)}$.

12. 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)}$, and extends the algorithm to any $L_p$ norm

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

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

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

Implementations

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

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

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

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

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

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

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

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

23. 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

24. 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

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

This algorithm provably solves SVP in time $2^n$ (achieving constant $c=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

• Bridging the gap between the theoretical running time of provable sieve/combinatorial algorithms $2^n$ and heuristic variants $2^{0.297n}$. Can the proof of the running time of heuristic algorithms be made rigorous? Can the running time of theoretical algorithms be further improved to match the constant in the exponent claimed by heuristics?

• Finding a lattice sieve algorithm that solve other lattice problems (like CVP) exactly and in single exponential time. Currently, sieve algorithms provide exact solutions to SVP, but only guarantee $(1+\epsilon)$-approximations to other lattice problems like CVP, SIVP. Exact solutions to CVP, etc. running in time $2^{O(n)}$ have been discovered using alternative approaches based on Voronoi cell computations. But sieving techniques may lead to more efficient/practical algorithms.

• Determining the smallest constant $c$ such that SVP can be solved in time $2^{cn}$ is an important open problem. Heuristic versions of lattice sieve algorithms currently provide the best known constant $c=0.297$, and are among the most promising approaches to fast SVP algorithms.

• Much work on optimizing sieve algorithms has focused on the euclidean norm so far. It would be interesting to invesigate lattice sieve algorithms with respect to other norms (e.g. $L_1$ or $L_\infty$), and the best running time $2^{cn}$ they can achieve.

• Sieve algorithms use exponential space. While this seems intrinsic in the techniques employed by these algorithms, devising algorithms with similar running time, but using only polynomial space, is an important open problem.

PhD Theses

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

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