Sieve algorithms for the shortest vector problem are practical
From MaRDI portal
Publication:3537523
DOI10.1515/JMC.2008.009zbMath1193.11117WikidataQ59792864 ScholiaQ59792864MaRDI QIDQ3537523
Phong Q. Nguyen, Thomas Vidick
Publication date: 7 November 2008
Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)
Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06)
Related Items
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
