Lattice Problems and Lattice Sieving

This talk provides an introduction to lattice reduction, with an emphasis on the recent, rapidly improving exponential-space sieving algorithms. The lattice problem of interest is closely related to integer programming: both involve finding integer points, but in ellipsoids for lattices and in polytopes for integer programming. The demand for cryptographic applications has driven remarkable progress in lattice sieving over the last decade. We will present the best publicly known lattice sieving algorithms, their performance, and record-breaking computations. We will also discuss how to resolve the issues caused by exponential-space complexity when developing practical lattice solvers. For the largest practically solvable lattice problems, sieving algorithms can be roughly $2^{15}$ to $2^{20}$ times faster than classical enumeration algorithms with $n^{cn}$ time complexity, while memory consumption remains a minor part of the overall cost.