Smoothing Parameter and Shortest Vector Problem on Random Lattices
Amaury Pouly, Yixin Shen · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
Lattice problems have many applications in various domains of computer science. There is currently a gap in the understanding of these problems with respect to their worst-case complexity and their average-case behaviour. For instance, the Shortest Vector problem (SVP) on an n-dimensional lattice has worst-case complexity 2 n+o (n) [2]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity 2 0.292n+o (n) [11] to assess the security of latticebased cryptography schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography, which are usually random in some way 1 . In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developped by Siegel [36], we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies to almost all random lattices. This allows us to obtain a 2 n/2+o(n) time algorithm for an approximation version of the SVP on random lattices with a small constant approximation factor.