TY - GEN
T1 - Solving the shortest vector problem in 2n time via discrete Gaussian sampling
AU - Aggarwal, Divesh
AU - Dadush, Daniel
AU - Regev, Oded
AU - Stephens-Davidowitz, Noah
N1 - Publisher Copyright:
© Copyright 2015 ACM.
PY - 2015/6/14
Y1 - 2015/6/14
N2 - 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 Õ(4n)-time and Õ(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.
AB - 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 Õ(4n)-time and Õ(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.
KW - Discrete Gaussian
KW - Lattices
KW - Shortest Vector Problem
UR - http://www.scopus.com/inward/record.url?scp=84958771669&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958771669&partnerID=8YFLogxK
U2 - 10.1145/2746539.2746606
DO - 10.1145/2746539.2746606
M3 - Conference contribution
AN - SCOPUS:84958771669
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 733
EP - 742
BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015
Y2 - 14 June 2015 through 17 June 2015
ER -