Paper 2024/1805

Solving the Shortest Vector Problem in $2^{0.63269n+o(n)}$ time on Random Lattices

Abstract

The Shortest Vector problem (SVP) is the most important problem in lattice-based cryptanalysis. There is currently a gap in the understanding of this problem with respect to its worst-case complexity and its average-case behaviour. For instance, SVP on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ [ADRS15]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ [BDGL16] to assess the security of lattice-based cryptography schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography, which are usually random in some way. In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developed by Siegel, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies to almost all random lattices. Using a known discrete Gaussian sampler at the smoothing parameter, we can then directly sample short vectors. This allows us to provably solve an approximation version of the SVP on almost all random lattices with a small constant approximation factor $1.123$, in time $2^{n/2+o(n)}$. With further analysis, we can provably solve the exact SVP in time $2^{0.63269n+o(n)}$ on almost all random lattices as well. We also provide a smooth time approximation factor tradeoff between these two cases. All our algorithms work in space $2^{n/2+o(n)}$. Our paper is a first step towards better understanding the heuristic behaviour of lattice sieving on random lattices.

Note: This new version substantially changes the paper: there is a now a bound on the Gaussian mass of the lattice intersected with a ball. Furthermore, we have significantly improved the proof so that we can now solve exact SVP as well and the complexity of approx-SVP is improved as well.