A sieve algorithm based on overlattices

DOI10.1112/S1461157014000229MaRDI QIDQ2878827zbMATH OpenFDO

Authors Anja Becker, Nicolas Gama, Antoine Joux

Publication date 5 September 2014

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/S1461157014000229

zbMATH Keywords

closest vector, quasi-orthonormal basisheuristic algorithmoverlatticeshortest vector

Mathematics Subject Classification ID

Geometry of numbers (11H99) Applications of sieve methods (11N36) Number-theoretic algorithms; complexity (11Y16) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A sieve algorithm for the shortest lattice vector problem
• Sieve algorithms for the shortest vector problem are practical
• Shortest vector from lattice sieving: a few dimensions for free
• Faster exponential time algorithms for the shortest vector problem
• A three-level sieve algorithm for the shortest vector problem

Cites work

• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
• Analyzing blockwise lattice algorithms using dynamical systems
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
• Factoring polynomials with rational coefficients
• Higher-dimensional analogs of Hermite's constant
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Improved Generic Algorithms for Hard Knapsacks
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice enumeration using extreme pruning
• Lattice reduction: a toolbox for the cryptoanalyst
• On Positive Definite Quadratic Forms
• Radon transforms and packings
• Rankin’s Constant and Blockwise Lattice Reduction
• Sieve algorithms for the shortest vector problem are practical

Cited in

(17)

• 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
• The irreducible vectors of a lattice: some theory and applications
• (EC)DSA lattice attacks based on Coppersmith's method
• Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
• Nearest planes in practice
• A three-level sieve algorithm for the shortest vector problem
• scientific article; zbMATH DE number 4168803 (Why is no real title available?)
• Sieve algorithms for the shortest vector problem are practical
• Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm
• Hermite’s Constant and Lattice Algorithms
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Faster exponential time algorithms for the shortest vector problem
• Improved algorithms for the approximate k-List problem in Euclidean norm
• Sieve algorithms for some orthogonal integer lattices
• Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
• Finding shortest lattice vectors faster using quantum search

This page was built for publication: A sieve algorithm based on overlattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878827)