### 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 Õ(4^{n})-time and Õ(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. 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.

Original language | English (US) |
---|---|

Title of host publication | STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 733-742 |

Number of pages | 10 |

ISBN (Electronic) | 9781450335362 |

DOIs | |

State | Published - Jun 14 2015 |

Event | 47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States Duration: Jun 14 2015 → Jun 17 2015 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 14-17-June-2015 |

ISSN (Print) | 0737-8017 |

### Other

Other | 47th Annual ACM Symposium on Theory of Computing, STOC 2015 |
---|---|

Country | United States |

City | Portland |

Period | 6/14/15 → 6/17/15 |

### Fingerprint

### Keywords

- Discrete Gaussian
- Lattices
- Shortest Vector Problem

### ASJC Scopus subject areas

- Software

### Cite this

^{n}time via discrete Gaussian sampling. In

*STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing*(pp. 733-742). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746606