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

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