Enumeration-based Lattice Reduction
Shi Bai – Florida Atlantic University
Lattice reduction algorithms have received much attention in recent years due to their relevance in cryptography. In this talk, we will discuss some of the recent developments on enumeration-based lattice reduction algorithms.
First, we will discuss a lattice reduction algorithm that achieves root Hermite factor k^(1/(2k)) in time k^(k/8 + o(k)) and polynomial memory. This improves the previously best known enumeration-based algorithms which achieve the same quality, but in time k^(k/(2e) +o(k)). The main idea is to conduct the preprocessing in a larger dimension than the enumerate dimension. Second, we discuss the usage of approximate enumeration oracles in BKZ, together with extended preprocessing ideas. In the end, we will illustrate some simulated results to demonstrate their practical behavior.
This talk is based on the following joint work:
M. R. Albrecht, S. Bai, P. A. Fouque, P. Kirchner, D. Stehlé, W. Wen: Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k^(1/(2k)) Time k^(k/8+o(k)). CRYPTO (2) 2020: 186-212.
M. R. Albrecht, S. Bai, J. Li, J. Rowell: Lattice Reduction with Approximate Enumeration Oracles – Practical Algorithms and Concrete Performance. CRYPTO (2) 2021: 732-759.