Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices

DOI10.1007/978-3-642-19094-0_11zbMath1318.94080OpenAlexW1556199233MaRDI QIDQ3078387

Michael Schneider

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_11

zbMATH Keywords

shortest vector problemlattice reductionsieving algorithms

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (3)

Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Gauss Sieve Algorithm on GPUs

Uses Software

• fpLLL

Cites Work

• Unnamed Item
• Sampling methods for shortest vectors, closest vectors and successive minima
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
• Sieve algorithms for the shortest vector problem are practical
• Parallel Shortest Lattice Vector Enumeration on Graphics Cards
• Lattice Enumeration Using Extreme Pruning
• Accelerating Lattice Reduction with FPGAs
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• On the equidistribution of Hecke points
• A sieve algorithm for the shortest lattice vector problem
• Predicting Lattice Reduction
• Algorithmic Number Theory

This page was built for publication: Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices