A sieve algorithm based on overlattices
From MaRDI portal
Publication:2878827
DOI10.1112/S1461157014000229zbMath1296.11090MaRDI QIDQ2878827
Antoine Joux, Nicolas Gama, Anja Becker
Publication date: 5 September 2014
Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)
Approximation methods and heuristics in mathematical programming (90C59) Number-theoretic algorithms; complexity (11Y16) Applications of sieve methods (11N36) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Geometry of numbers (11H99)
Related Items
(EC)DSA lattice attacks based on Coppersmith's method, Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing, Finding shortest lattice vectors faster using quantum search, Sieving for closest lattice vectors (with preprocessing), A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
Cites Work
- Factoring polynomials with rational coefficients
- Lattice reduction: a toolbox for the cryptoanalyst
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Higher-dimensional analogs of Hermite's constant
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Improved Generic Algorithms for Hard Knapsacks
- A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- Sieve algorithms for the shortest vector problem are practical
- Lattice Enumeration Using Extreme Pruning
- Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
- Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
- Rankin’s Constant and Blockwise Lattice Reduction
- On Positive Definite Quadratic Forms
- Radon transforms and packings
