Abstract

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