Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
From MaRDI portal
Publication:2941568
DOI10.1145/2746539.2746606zbMath1321.68426arXiv1412.7994OpenAlexW2168596303WikidataQ57567986 ScholiaQ57567986MaRDI QIDQ2941568
Noah Stephens-Davidowitz, Divesh Aggarwal, Daniel Dadush, Oded Regev
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.7994
Related Items (33)
Lower bounds on lattice sieving and information set decoding ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Voronoi Cells of Lattices with Respect to Arbitrary Norms ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography ⋮ Minimization of even conic functions on the two-dimensional integral lattice ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Finding shortest lattice vectors faster using quantum search ⋮ An Inequality for Gaussians on Lattices ⋮ Sampling the Riemann-theta Boltzmann machine ⋮ Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice ⋮ On the asymptotic complexity of solving LWE ⋮ Complexity of optimizing over the integers ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Lattice-based locality sensitive hashing is optimal ⋮ Discrete Gaussian Distributions via Theta Functions ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ Unnamed Item ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ Exact lattice sampling from non-Gaussian distributions ⋮ How (Not) to Instantiate Ring-LWE ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Kissing Numbers and Transference Theorems from Generalized Tail Bounds ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
Uses Software
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
This page was built for publication: Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
