Paper 2024/1805

Solving the Shortest Vector Problem in 20.63269n+o(n) time on Random Lattices

Amaury Pouly, French National Centre for Scientific Research
Yixin Shen, Univ Rennes, Inria, CNRS, IRISA, Rennes, France
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 2n+o(n) [ADRS15]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity 20.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 , in time . With further analysis, we can provably solve the exact SVP in time 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 . 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Random LatticesSmoothing ParameterShortest Vector Problem
Contact author(s)
amaury pouly @ cnrs fr
yixin shen @ inria fr
History
2025-02-14: revised
2024-11-04: received
See all versions
Short URL
https://ia.cr/2024/1805
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1805,
      author = {Amaury Pouly and Yixin Shen},
      title = {Solving the Shortest Vector Problem in $2^{0.63269n+o(n)}$ time on Random Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1805},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1805}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.