Sieve algorithms for the shortest vector problem are practical
From MaRDI portal
Publication:3537523
DOI10.1515/JMC.2008.009zbMATH Open1193.11117DBLPjournals/jmc/NguyenV08WikidataQ59792864 ScholiaQ59792864MaRDI QIDQ3537523FDOQ3537523
Authors: Phong Q. Nguyen, Thomas Vidick 
Publication date: 7 November 2008
Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)
Recommendations
Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)
Cites Work
- A hierarchy of polynomial time lattice basis reduction algorithms
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- On Lovász' lattice reduction and the nearest lattice point problem
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
- Closest point search in lattices
- On the equidistribution of Hecke points
- On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
- Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
- Lattice coverings of space
- Rankin’s Constant and Blockwise Lattice Reduction
Cited In (71)
- Finding shortest lattice vectors faster using quantum search
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Rigorous and Efficient Short Lattice Vectors Enumeration
- A survey of solving SVP algorithms and recent strategies for solving the SVP challenge
- Title not available (Why is that?)
- Lattice-based cryptography: a survey
- A fast phase-based enumeration algorithm for SVP challenge through \(y\)-sparse representations of short lattice vectors
- A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
- Lattice-based key exchange on small integer solution problem
- Lattice Sieving via Quantum Random Walks
- Shortest vector from lattice sieving: a few dimensions for free
- Sieving for closest lattice vectors (with preprocessing)
- Title not available (Why is that?)
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- Predicting Lattice Reduction
- Hypercube LSH for approximate near neighbors
- Approximate Voronoi cells for lattices, revisited
- Advanced lattice sieving on GPUs, with tensor cores
- The randomized slicer for CVPP: sharper, faster, smaller, batchier
- How to meet ternary LWE keys
- Algorithms for the shortest and closest lattice vector problems
- The general sieve kernel and new records in lattice reduction
- Solving market split problems with heuristical lattice reduction
- Application of mixed integer quadratic program to shortest vector problems
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- Cloud-assisted LLL: a secure and efficient outsourcing algorithm for approximate shortest vector problem
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Finding shortest lattice vectors in the presence of gaps
- Gauss sieve algorithm on GPUs
- Improved algorithms for the approximate \(k\)-List problem in Euclidean norm
- Sieve algorithms for some orthogonal integer lattices
- Lattice-based algorithms for number partitioning in the hard phase
- Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
- Hermite’s Constant and Lattice Algorithms
- 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
- Slide reduction, revisited -- filling the gaps in SVP approximation
- Computing efficiently the lattice width in any dimension
- Faster exponential time algorithms for the shortest vector problem
- A three-level sieve algorithm for the shortest vector problem
- Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
- Accelerating lattice reduction with FPGAs
- A sieve algorithm for the shortest lattice vector problem
- Tuple lattice sieving
- Estimating quantum speedups for lattice sieves
- A sieve algorithm based on overlattices
- Analysis of Gauss-sieve for solving the shortest vector problem in lattices
- Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
- Sieve, Enumerate, Slice, and Lift:
- Lower bounds on lattice sieving and information set decoding
- A lattice reduction algorithm based on sublattice BKZ
- The irreducible vectors of a lattice: some theory and applications
- Kissing numbers and transference theorems from generalized tail bounds
- Does the dual-sieve attack on learning with errors even work?
- Finding short integer solutions when the modulus is small
- Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS
- Estimating the hidden overheads in the BDGL lattice sieving algorithm
- Concrete analysis of quantum lattice enumeration
- Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
- Asymptotics and improvements of sieving for codes
- Provable dual attacks on learning with errors
- BS: Blockwise Sieve Algorithm for Finding Short Vectors from Sublattices
- Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- On the SVP for low-dimensional circulant lattices
- Formally verifying Kyber. Episode V: machine-checked IND-CCA security and correctness of ML-KEM in Easycrypt
- CryptAttackTester: high-assurance attack analysis
- Quantum lattice enumeration in limited depth
- Classical and Quantum 3 and 4-Sieves to Solve SVP with Low Memory
- New NTRU Records with Improved Lattice Bases
- Finding shortest vector using quantum NV sieve on Grover
This page was built for publication: Sieve algorithms for the shortest vector problem are practical
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3537523)
