Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm

DOI10.1007/978-3-540-74143-5_10zbMath1215.94050OpenAlexW2160639384MaRDI QIDQ3612549

Guillaume Hanrot, Damien Stehlé

Publication date: 10 March 2009

Published in: Advances in Cryptology - CRYPTO 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74143-5_10

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (35)

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Improvements in closest point search based on dual HKZ-bases ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ On the asymptotic complexity of solving LWE ⋮ Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation ⋮ Improving convergence and practicality of slide-type reductions ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ Reducing number field defining polynomials: an application to class group computations ⋮ Sieve algorithms for the shortest vector problem are practical ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Second order statistical behavior of LLL and BKZ ⋮ Random Sampling Revisited: Lattice Enumeration with Discrete Pruning ⋮ Hermite’s Constant and Lattice Algorithms ⋮ LLL: A Tool for Effective Diophantine Approximation ⋮ Rigorous and Efficient Short Lattice Vectors Enumeration ⋮ Approximate Voronoi cells for lattices, revisited ⋮ A Digital Signature Scheme Based on CVP  ∞ ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Subexponential time relations in the class group of large degree number fields ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ The convergence of slide-type reductions ⋮ Cryptography Based on Quadratic Forms: Complexity Considerations ⋮ Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\) ⋮ Unnamed Item ⋮ A sieve algorithm based on overlattices ⋮ Subexponential class group and unit group computation in large degree number fields

This page was built for publication: Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm