Paper 2024/1805
Solving the Shortest Vector Problem in 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
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
-
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} }