A 2ⁿ/2-time algorithm for n -SVP and n -Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
From MaRDI portal
Publication:2056696
Cites work
- A decade of lattice cryptography
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A hierarchy of polynomial time lattice basis reduction algorithms
- A reverse Minkowski theorem
- A sieve algorithm based on overlattices
- A sieve algorithm for the shortest lattice vector problem
- An Inequality for Gaussians on Lattices
- Approximating the densest sublattice from Rankin's inequality
- Classical hardness of learning with errors
- Factoring polynomials with rational coefficients
- Finding short lattice vectors within Mordell's inequality
- Finding shortest lattice vectors in the presence of gaps
- Hardness of SIS and LWE with small parameters
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- Improved discrete Gaussian and Subgaussian analysis for lattice cryptography
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- New directions in nearest neighbor searching with applications to lattice sieving
- On lattices, learning with errors, random linear codes, and cryptography
- Practical, Predictable Lattice Basis Reduction
- Shortest vector from lattice sieving: a few dimensions for free
- Sieve algorithms for the shortest vector problem are practical
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Slide reduction, revisited -- filling the gaps in SVP approximation
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic cryptosystems
- The probabilistic method
- Trapdoors for hard lattices and new cryptographic constructions
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Cited in
(5)- Lattice problems beyond polynomial time
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Wagner's algorithm provably runs in subexponential time for \(\mathrm{SIS}^\infty \)
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Solving the shortest vector problem in \(2^{0.63269n+o(n)}\) time on random lattices
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056696)
