2015

# Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

## Publication

### Publication

*Presented at the ACM Symposium on Theory of Computing*

We give a randomized 2n+o(n)-time and space algorithm for
solving the Shortest Vector Problem (SVP) on n-dimensional
Euclidean lattices. This improves on the previous fastest algorithm:
the deterministic eO (4n)-time and eO(2n)-space algorithm
of Micciancio and Voulgaris (STOC 2010, SIAM J.
Comp. 2013).
In fact, we give a conceptually simple algorithm that solves
the (in our opinion, even more interesting) problem of discrete
Gaussian sampling (DGS). More specifically, we show
how to sample 2n/2 vectors from the discrete Gaussian distribution
at any parameter in 2n+o(n) time and space. (Prior work
only solved DGS for very large parameters.) Our SVP result
then follows from a natural reduction from SVP to DGS.
In addition, we give a more refined algorithm for DGS
above the so-called smoothing parameter of the lattice, which
can generate 2n/2 discrete Gaussian samples in just 2n/2+o(n)
time and space. Among other things, this implies a 2n/2+o(n)-
time and space algorithm for 1.93-approximate decision SVP.

Additional Metadata | |
---|---|

doi.org/10.1145/2746539.2746606 | |

ACM Symposium on Theory of Computing | |

Organisation | Networks and Optimization |

Aggarwal, D, Dadush, D.N, Regev, O, & Stephens-Davidowitz, N. (2015). Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling. In
Proceedings of ACM Symposium on Theory of Computing 2015 (STOC) (pp. 733–742). doi:10.1145/2746539.2746606 |