SVP · Classical · worst case — CryptoRecords.info

Classical · worst case

Exact Euclidean SVP on arbitrary full-rank lattices

20 results · 18 papers

ClassicalProvableWorst case2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Superlattice methods for the shortest vector problem and discrete Gaussian samplingMinki Hhan · Jiseung Kim · Sunyeop Kim · Thijs LaarhovenePrint 2026/2761Source BibTeX / detailsarbitrary lattices Euclidean	4 Nov 2026	2^{0.409 n + o(n)}	2^{0.259 n + o(n)}	PreprintSource checked
2	Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingYiming Gao · Xuyuan Han · Honggang HuePrint 2026/2690Source BibTeX / detailsarbitrary lattices Euclidean	30 Oct 2026	2^{0.4130 n + o(n)}	2^{0.3138 n + o(n)}	PreprintSource checked
3	Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference TreeMinki HhanePrint 2026/1859Source BibTeX / detailsarbitrary lattices Euclidean	2 Sept 2026	2^{n/2 + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
4	Solving the Shortest Vector Problem in 2^(0.6039n) Time via Mid-point HessianMinki HhanePrint 2026/1597Source BibTeX / detailsarbitrary lattices Euclidean	3 Aug 2026	2^{0.6039 n + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
5	Solving the Shortest Vector Problem in 2^(0.7314n+o(n)) Time via Discrete Gaussian Sampling on SuperlatticesYiming Gao · Yansong Feng · Honggang HuePrint 2026/1587Source BibTeX / detailsarbitrary lattices Euclidean	3 Aug 2026	2^{0.7314 n + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
6	One Discrete Gaussian Sample in 2^{n/2+o(n)} TimeJiseung KimarXiv 2608.03220Source BibTeX / detailsclassical provable arbitrary lattices discrete Gaussian sampling random superlattices	4 Aug 2026	2^{c₀ n + o(n)}, c₀ ≈ 0.7315	2^{n/2 + o(n)}	PreprintSource checked
7	Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingDivesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-DavidowitzSTOC 2015Source BibTeX / detailsarbitrary lattices Euclidean	26 Dec 2014	2^{n + o(n)}	2^{1 n + o(n)}	PublishedSource checked
7	Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)Divesh Aggarwal · Noah Stephens-DavidowitzSOSA 2018Source BibTeX / detailsclassical provable arbitrary lattices	5 Sept 2017	2^{1 n + o(n)}	2^{1 n + o(n)}	PublishedSource checked
9	Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance DecodingDivesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin ShenSIAM Journal on Computing 2025Source BibTeX / detailsprovable time-space tradeoff	10 May 2022	2^{1.669 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
10	A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell ComputationsDaniele Micciancio · Panagiotis VoulgarisSIAM Journal on Computing 2013Source BibTeX / detailsarbitrary lattices Euclidean	2011	2^{2 n + o(n)}	2^{1 n + o(n)}	PublishedSource checked
11	Space-efficient classical and quantum algorithms for the shortest vector problemYanlin Chen · Kai-Min Chung · Ching-Yi LaiQuantum Information and Computation 2018Source BibTeX / detailsclassical provable arbitrary lattices time–space trade-off half-exponential space	31 Aug 2017	2^{2.05 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
12	Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ℓ_p normPriyanka MukhopadhyayAlgorithms 2021Source BibTeX / detailsclassical provable arbitrary lattices	9 Jul 2019	2^{2.25 n + o(n)}	—	PublishedSource checked
13	Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)Xavier Pujol · Damien StehléePrint 2009/605Source BibTeX / detailsarbitrary lattices Euclidean	9 Dec 2009	2^{2.465 n + o(n)}	2^{1.233 n + o(n)}	PublishedSource checked
14	Algorithms for the Shortest and Closest Lattice Vector ProblemsGuillaume Hanrot · Xavier Pujol · Damien StehléIWCC 2011Source BibTeX / detailsclassical provable arbitrary lattices	2013	2^{2.648 n + o(n)}	2^{1.325 n + o(n)}	PublishedSource checked
15	Faster exponential time algorithms for the shortest vector problemDaniele Micciancio · Panagiotis VoulgarisSODA 2010Source BibTeX / detailsclassical provable arbitrary lattices	10 Aug 2009	2^{3.199 n + o(n)}	2^{1.325 n + o(n)}	PublishedSource checked
16	Algorithms for the Shortest and Closest Lattice Vector ProblemsGuillaume Hanrot · Xavier Pujol · Damien StehléIWCC 2011Source BibTeX / detailsclassical provable arbitrary lattices	2013	2^{3.397 n + o(n)}	2^{1.984 n + o(n)}	PublishedSource checked
17	Sieve Algorithms for the Shortest Vector Problem are PracticalPhong Q. Nguyen · Thomas VidickJournal of Mathematical Cryptology 2008Source BibTeX / detailsclassical provable arbitrary lattices	11 Sept 2008	2^{5.9 n + o(n)}	2^{2.95 n + o(n)}	PublishedSource checked
18	2^{O(n)}-time algorithm for SVPOded Regev · Michael KhanevskyLattices in Computer Science, Lecture 8 2004Source BibTeX / detailsclassical provable arbitrary lattices	2004	2^{16 n + o(n)}	2^{8 n + o(n)}	PreprintSource checked
—	A sieve algorithm for the shortest lattice vector problemMiklós Ajtai · Ravi Kumar · Dandapani SivakumarSTOC 2001Source BibTeX / detailsclassical provable arbitrary lattices	6 Jul 2001	2^O(n)	2^O(n)	PublishedSource checked
—	Faster exponential time algorithms for the shortest vector problemDaniele Micciancio · Panagiotis VoulgarisSODA 2010Source BibTeX / detailsclassical provable arbitrary lattices time–space trade-off	10 Aug 2009	2^O(n)	2^{1.095 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Exact Euclidean SVP on arbitrary full-rank lattices
Computation: Classical
Rigor: Provable
Instances: Worst case
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: The history of proven asymptotic bounds for exact SVP. Recent preprints remain explicitly marked.
Comparison rules: Return a shortest nonzero vector in an arbitrary n-dimensional Euclidean lattice. Compare the coefficient c in 2^{c n+o(n)} time; polynomial input-size factors are suppressed. Record space separately.
Tags: arbitrary lattices, Euclidean