Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)

DOI10.4230/OASICS.SOSA.2018.12zbMath1433.68474arXiv1709.01535OpenAlexW2963101940MaRDI QIDQ5240427

Noah Stephens-Davidowitz, Divesh Aggarwal

Publication date: 25 October 2019

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

zbMATH Keywords

latticesshortest vector problemclosest vector problemCVPSVP

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (13)

Covering convex bodies and the closest vector problem ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Unnamed Item ⋮ On Gaussian sampling, smoothing parameter and application to signatures ⋮ Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem ⋮ Deciding whether a lattice has an orthonormal basis is in co-NP ⋮ On compact representations of Voronoi cells of lattices ⋮ 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 ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation

Uses Software

• FrodoKEM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lovász' lattice reduction and the nearest lattice point problem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• New bounds in some transference theorems in the geometry of numbers
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Approximating CVP to within almost-polynomial factors is NP-hard
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• A Decade of Lattice Cryptography
• Practical, Predictable Lattice Basis Reduction
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Integer Programming with a Fixed Number of Variables
• A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
• Some optimal codes have structure
• Hardness of approximating the shortest vector problem in lattices
• Trapdoors for hard lattices and new cryptographic constructions
• Minkowski's Convex Body Theorem and Integer Programming
• New directions in nearest neighbor searching with applications to lattice sieving
• A sieve algorithm for the shortest lattice vector problem
• An Inequality for Gaussians on Lattices
• Classical hardness of learning with errors
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)