The Shortest Vector problem (SVP) is one of 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 has worst-case complexity \(2^{n+o(n)}\) on an n-dimensional lattice [2]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity \(2^{0.292n+o(n)}\) [10] 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 (There exists several formal notions of random lattices). 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 [45], 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 also provably solve the exact SVP in time \(2^{0.63269n+o(n)}\) on most random lattices. We also provide a smooth time/approximation factor tradeoff between these two cases. All our algorithms work in space \(2^{n/2+o(n)}\) .