Spring 2020

What is Lattice Point Enumeration Up to These Days?

Tuesday, Jun. 15, 2021 9:00 am9:30 am PDT

Add to Calendar


Martin Albrecht (Royal Holloway, University of London)



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

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