Sieve algorithms for the shortest vector problem are practical

DOI10.1515/JMC.2008.009zbMath1193.11117DBLPjournals/jmc/NguyenV08WikidataQ59792864 ScholiaQ59792864MaRDI QIDQ3537523

Phong Q. Nguyen, Thomas Vidick

Publication date: 7 November 2008

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

zbMATH Keywords

enumerationlatticessieveLLLAKS algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items (48)

Lattice-based key exchange on small integer solution problem ⋮ How to meet ternary LWE keys ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Lattice Sieving via Quantum Random Walks ⋮ Sieve algorithms for some orthogonal integer lattices ⋮ Does the dual-sieve attack on learning with errors even work? ⋮ Finding short integer solutions when the modulus is small ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Lattice-based cryptography: a survey ⋮ Estimating quantum speedups for lattice sieves ⋮ Tuple lattice sieving ⋮ Computing efficiently the lattice width in any dimension ⋮ A lattice reduction algorithm based on sublattice BKZ ⋮ The irreducible vectors of a lattice: some theory and applications ⋮ Gauss Sieve Algorithm on GPUs ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Solving market split problems with heuristical lattice reduction ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ Hermite’s Constant and Lattice Algorithms ⋮ Rigorous and Efficient Short Lattice Vectors Enumeration ⋮ Unnamed Item ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Predicting Lattice Reduction ⋮ Unnamed Item ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ Unnamed Item ⋮ A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices ⋮ Kissing Numbers and Transference Theorems from Generalized Tail Bounds ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ A sieve algorithm based on overlattices

Cites Work

• On Lovász' lattice reduction and the nearest lattice point problem
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• A hierarchy of polynomial time lattice basis reduction algorithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Lattice coverings of space
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• Closest point search in lattices
• On the equidistribution of Hecke points
• Rankin’s Constant and Blockwise Lattice Reduction

This page was built for publication: Sieve algorithms for the shortest vector problem are practical