Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

Abstract

The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.

Cited by in corpus (13)

• Decoding by Sampling: A Randomized Lattice Algorithm for Bounded Distance Decoding
• Towards security recommendations for public-key infrastructures for production environments in the post-quantum era
• A new Lenstra-type Algorithm for Quasiconvex Polynomial Integer Minimization with Complexity 2^O(n log n)
• Variational quantum solutions to the Shortest Vector Problem
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
• On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$
• A Deterministic Polynomial Space Construction for eps-nets under any Norm
• The nearest-colattice algorithm
• Space-efficient classical and quantum algorithms for the shortest vector problem
• An Efficient Optimal Algorithm for the Successive Minima Problem
• On Bounded Integer Programming
• Improvements in closest point search based on dual HKZ-bases
• The implementation of the parallel shortest vector enumerate in the block Korkin-Zolotarev method