SVP · Classical · heuristic — CryptoRecords.info

Classical · heuristic

Euclidean SVP under sieve heuristics

14 results · 14 papers

ClassicalHeuristicHeuristic random lists2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	New directions in nearest neighbor searching with applications to lattice sievingAnja Becker · Léo Ducas · Nicolas Gama · Thijs LaarhovenSODA 2016Source BibTeX / details	23 Nov 2015	(3/2)^{n/2 + o(n)}	2^{0.20751874963942188 n + o(n)}	PublishedSource checked
1	Shortest Vector from Lattice Sieving: a Few Dimensions for FreeLéo DucasEurocrypt 2018Source BibTeX / detailsheuristic dimensions for free subexponential improvement	11 Oct 2017	(3/2)^{n/2 + o(n)}	—	PublishedSource checked
3	Faster sieving for shortest lattice vectors using spherical locality-sensitive hashingThijs Laarhoven · Benne de WegerLatincrypt 2015Source BibTeX / details	6 Mar 2015	2^{0.2972 n + o(n)}	—	PublishedSource checked
3	Efficient (ideal) lattice sieving using cross-polytope LSHAnja Becker · Thijs LaarhovenAfricacrypt 2016Source BibTeX / details	24 Aug 2015	2^{0.2972 n + o(n)}	—	PublishedSource checked
5	Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor searchAnja Becker · Nicolas Gama · Antoine JouxePrint 2015/522Source BibTeX / details	31 May 2015	2^{0.3112 n + o(n)}	2^{0.2075 n + o(n)}	PreprintSource checked
6	Sieving for shortest vectors in lattices using angular locality-sensitive hashingThijs LaarhovenCrypto 2015Source BibTeX / details	26 Sept 2014	2^{0.3366 n + o(n)}	2^{0.2075 n + o(n)}	PublishedSource checked
7	Classical and quantum 3 and 4-sieves to solve SVP with low memoryAndré Chailloux · Johanna LoyerPQCrypto 2023Source BibTeX / detailsheuristic triple sieving tailored LSF memory tradeoff	2 Aug 2023	2^{0.3383 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
8	Speed-ups and time-memory trade-offs for tuple lattice sievingGottfried Herold · Elena Kirshanova · Thijs LaarhovenPKC 2018Source BibTeX / detailsheuristic triple sieving memory tradeoff	22 Dec 2017	2^{0.3588 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
9	Improved Algorithms for the Approximate k-List Problem in Euclidean NormGottfried Herold · Elena KirshanovaPKC 2017Source BibTeX / detailsheuristic triple sieving memory tradeoff	26 Jan 2017	2^{0.3717 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
10	Solving shortest and closest vector problems: The decomposition approachAnja Becker · Nicolas Gama · Antoine JouxANTS 2014Source BibTeX / details	24 Oct 2013	2^{0.3774 n + o(n)}	2^{0.2925 n + o(n)}	PublishedSource checked
11	A Three-Level Sieve Algorithm for the Shortest Vector ProblemFeng Zhang · Yanbin Pan · Gengran HuSAC 2013Source BibTeX / details	22 Oct 2014	2^{0.3778 n + o(n)}	2^{0.2833 n + o(n)}	PublishedSource checked
12	Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector ProblemXiaoyun Wang · Mingjie Liu · Chengliang Tian · Jingguo BiAsiaCCS 2011Source BibTeX / details	21 Dec 2010	2^{0.3836 n + o(n)}	2^{0.2557 n + o(n)}	PublishedSource checked
13	Sieve Algorithms for the Shortest Vector Problem are PracticalPhong Q. Nguyen · Thomas VidickJournal of Mathematical Cryptology 2008Source BibTeX / details	11 Sept 2008	(4/3)^{n + o(n)}	2^{0.20751874963942188 n + o(n)}	PublishedSource checked
14	Tuple lattice sievingShi Bai · Thijs Laarhoven · Damien StehléLMS Journal of Computation and Mathematics 2016Source BibTeX / detailsheuristic triple sieving memory tradeoff	21 Jul 2016	2^{0.4812 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Euclidean SVP under sieve heuristics
Computation: Classical
Rigor: Heuristic
Instances: Heuristic random lists
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Sieving bounds whose analysis relies on heuristic list-distribution assumptions.
Comparison rules: State the sieve heuristic and memory model. A heuristic exponent cannot be entered as a worst-case provable result. No practical timing or concrete-security claim follows from the leading exponent alone.
Tags