Report title: Slide reduction, revisited—filling the gaps in svp approximation

Reported by: Li Jianwei Research Fellow

Host: Professor Cao Zhenfu

Report time: March 22nd, 16:00-17:00

Report location: B1002, Science Building (online lecture, attended on-site)

Abstract:

Lattice reduction is a key tool in cryptanalysis at large, and is of course a central interest for the cryptanalysis of lattice-based cryptography. In this talk, we present how to generalize Gama and Nguyen’s slide reduction algorithm [STOC ’08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We also show a different algorithm that works when the block size is quite large—at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors.