What is Lattice Point Enumeration Up to These Days?
Martin Albrecht (Royal Holloway, University of London)
Zoom
I plan to cover recent works on improving lattice point enumeration as a subroutine of blockwise lattice reduction.
- Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance
Martin R. Albrecht, Shi Bai, Jianwei Li and Joe Rowell.
CRYPTO 2021 https://eprint.iacr.org/2020/1260
- Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))
Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé and Weiqiang Wen
CRYPTO 2020 https://eprint.iacr.org/2020/707
Together these works reduce the cost of reaching root Hermite factor ~ GH(400)^(1/400) from ~ 2^254 enumeration nodes when solving an SVP instance to ~2^196 nodes inside BKZ (per block).