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.