Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling. Aggarwal, D., Dadush, D., Regev, O., & Stephens-Davidowitz, N. In STOC, 2015. ![Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper Simons talk abstract bibtex 49 downloads We give a randomized $2^{n+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 $\widetilde{O}(4^n)$-time and $\widetilde{O}(2^n)$-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 $2^{n/2}$ vectors from the discrete Gaussian distribution at any parameter in $2^{n+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. We also show that our DGS algorithm implies a $2^{n + o(n)}$-time algorithm that approximates the Closest Vector Problem to within a factor of $1.97$. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate $2^{n/2}$ discrete Gaussian samples in just $2^{n/2+o(n)}$ time and space. Among other things, this implies a $2^{n/2+o(n)}$-time and space algorithm for $1.93$-approximate decision SVP.
@inproceedings{ADRSSolvingShortest15,
title = {Solving the {Shortest Vector Problem} in $2^n$ time via discrete {Gaussian} sampling},
abstract = {We give a randomized $2^{n+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 $\widetilde{O}(4^n)$-time and $\widetilde{O}(2^n)$-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 $2^{n/2}$ vectors from the discrete Gaussian distribution at any parameter in $2^{n+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. We also show that our DGS algorithm implies a $2^{n + o(n)}$-time algorithm that approximates the Closest Vector Problem to within a factor of $1.97$. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate $2^{n/2}$ discrete Gaussian samples in just $2^{n/2+o(n)}$ time and space. Among other things, this implies a $2^{n/2+o(n)}$-time and space algorithm for $1.93$-approximate decision SVP.},
url = {http://arxiv.org/abs/1412.7994},
booktitle = {STOC},
author = {Aggarwal, Divesh and Dadush, Daniel and Regev, Oded and {Stephens-Davidowitz}, Noah},
year = {2015},
url_Simons_talk = {http://www.youtube.com/watch?v=PWy0ZBRAUxA}
}
Downloads: 49
{"_id":"r7QzgERx6CjTCyLTx","bibbaseid":"aggarwal-dadush-regev-stephensdavidowitz-solvingtheshortestvectorproblemin2ntimeviadiscretegaussiansampling-2015","authorIDs":["NsKfZS8svvuZwZEBa"],"author_short":["Aggarwal, D.","Dadush, D.","Regev, O.","Stephens-Davidowitz, N."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling","abstract":"We give a randomized $2^{n+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 $\\widetilde{O}(4^n)$-time and $\\widetilde{O}(2^n)$-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 $2^{n/2}$ vectors from the discrete Gaussian distribution at any parameter in $2^{n+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. We also show that our DGS algorithm implies a $2^{n + o(n)}$-time algorithm that approximates the Closest Vector Problem to within a factor of $1.97$. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate $2^{n/2}$ discrete Gaussian samples in just $2^{n/2+o(n)}$ time and space. Among other things, this implies a $2^{n/2+o(n)}$-time and space algorithm for $1.93$-approximate decision SVP.","url":"http://arxiv.org/abs/1412.7994","booktitle":"STOC","author":[{"propositions":[],"lastnames":["Aggarwal"],"firstnames":["Divesh"],"suffixes":[]},{"propositions":[],"lastnames":["Dadush"],"firstnames":["Daniel"],"suffixes":[]},{"propositions":[],"lastnames":["Regev"],"firstnames":["Oded"],"suffixes":[]},{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2015","url_simons_talk":"http://www.youtube.com/watch?v=PWy0ZBRAUxA","bibtex":"@inproceedings{ADRSSolvingShortest15,\n title = {Solving the {Shortest Vector Problem} in $2^n$ time via discrete {Gaussian} sampling},\n abstract = {We give a randomized $2^{n+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 $\\widetilde{O}(4^n)$-time and $\\widetilde{O}(2^n)$-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 $2^{n/2}$ vectors from the discrete Gaussian distribution at any parameter in $2^{n+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. We also show that our DGS algorithm implies a $2^{n + o(n)}$-time algorithm that approximates the Closest Vector Problem to within a factor of $1.97$. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate $2^{n/2}$ discrete Gaussian samples in just $2^{n/2+o(n)}$ time and space. Among other things, this implies a $2^{n/2+o(n)}$-time and space algorithm for $1.93$-approximate decision SVP.},\n url = {http://arxiv.org/abs/1412.7994},\n booktitle = {STOC},\n author = {Aggarwal, Divesh and Dadush, Daniel and Regev, Oded and {Stephens-Davidowitz}, Noah},\n year = {2015},\n url_Simons_talk = {http://www.youtube.com/watch?v=PWy0ZBRAUxA}\n}\n\n","author_short":["Aggarwal, D.","Dadush, D.","Regev, O.","Stephens-Davidowitz, N."],"key":"ADRSSolvingShortest15","id":"ADRSSolvingShortest15","bibbaseid":"aggarwal-dadush-regev-stephensdavidowitz-solvingtheshortestvectorproblemin2ntimeviadiscretegaussiansampling-2015","role":"author","urls":{"Paper":"http://arxiv.org/abs/1412.7994"," simons talk":"http://www.youtube.com/watch?v=PWy0ZBRAUxA"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://www.noahsd.com/"}},"downloads":49},"bibtype":"inproceedings","biburl":"https://dl.dropbox.com/s/26018h26wgh5c2o/bibbase.bib","creationDate":"2020-12-14T08:01:23.331Z","downloads":49,"keywords":[],"search_terms":["solving","shortest","vector","problem","time","via","discrete","gaussian","sampling","aggarwal","dadush","regev","stephens-davidowitz"],"title":"Solving the Shortest Vector Problem in $2^n$ time via discrete Gaussian sampling","year":2015,"dataSources":["kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","DFNYHMG5naiXCbQWf","t7S757akkuDKXd4Lt","j49aoDnSSLjzndmof","bNuEGB6D6ArYKZG7X","rNfpY7KpfzEnPHFDu","mb294T8RPmLcqf4vP"]}