Classification of attacks against lattices

Question

I'm interested about the cryptanalysis side of lattice-based cryptography, and was wondering whether there is a survey paper or something that gives some classification of attacks against lattices, current state-of-the-art in each category, and how they relate to one another. For example, I see on one side there is lattice basis reduction such as LLL and its variants, then there seems to be sieving attacks, enumeration attacks, and some other approaches. How do these approaches relate to one another?

Answer 1

You're describing methods of solving LWE via reduction to SVP. In particular:

• Sieving and Enumeration are methods of solving exact SVP

• Basis reduction is a method of solving approximate SVP

There are additionally ways of solving LWE directly (the classic example is the Arora-Ge attack, which works when the noise distribution is too concentrated).

Daniele Micciancio has a webpage on lattice cryptography where you can see some discussion of this/links to papers.

While I haven't read the following thesis:

• Michael Walter's thesis has sections on both enumeration and basis reduction.

• Rachel Player's thesis seems to include include a summary of direct attacks on LWE, and a section of lattice basis reduction.