A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP

DOI10.1007/978-3-030-77870-5_17OpenAlexW3175089488MaRDI QIDQ2056696

Noah Stephens-Davidowitz, Divesh Aggarwal, Zeyong Li

Publication date: 8 December 2021

Full work available at URL: https://arxiv.org/abs/2007.09556

Mathematics Subject Classification ID

Searching and sorting (68P10) Cryptography (94A60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Shortest vector from lattice sieving: a few dimensions for free
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Finding Shortest Lattice Vectors in the Presence of Gaps
• A Decade of Lattice Cryptography
• Practical, Predictable Lattice Basis Reduction
• Hardness of SIS and LWE with Small Parameters
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• A sieve algorithm based on overlattices
• Approximating the densest sublattice from Rankin’s inequality
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
• Sieve algorithms for the shortest vector problem are practical
• Trapdoors for hard lattices and new cryptographic constructions
• New directions in nearest neighbor searching with applications to lattice sieving
• A reverse Minkowski theorem
• Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
• A sieve algorithm for the shortest lattice vector problem
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
• An Inequality for Gaussians on Lattices
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Classical hardness of learning with errors
• Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP