Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$

Emmanouil Doulgerakis, Thijs Laarhoven

In an attempt to close the gap between the best provable and heuristic algorithms for hard lattice problems, such as the shortest (SVP) and closest vector problem (CVP), we analyze…