Welcome to the resource topic for 2024/1805
Title:
Smoothing Parameter and Shortest Vector Problem on Random Lattices
Authors: Amaury Pouly, Yixin Shen
Abstract: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)} \cite{ADRS15}.
However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity 2^{0.292n+o(n)} \cite{BeckerDGL16}
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 developped by Siegel, 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.
ePrint: https://eprint.iacr.org/2024/1805
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .