Improvements in the analysis of Kannan's CVP algorithm

• Our paper revisits Kannan's CVP algorithm and points out a new method “sequence counting” to upper bound the time complexity by 20.401n+o(n)nn2.
• We connects the loops of the enumeration algorithm with lattice points by a one-to-one mapping using the “sequence” as a tool.
• We use different methods to upper bound the number of lattice points near a target vector according to the dimension of the lattice, and then combine them to conclude our result.

Finding a closest lattice vector to a given target vector is a widely studied problem in computational mathematics and computer science. The classical enumeration algorithm was given by Kannan in 1983 together with an algorithm for the shortest vector problem. The time complexity of the closest vector enumeration algorithm based on HKZ-reduced bases was proven to within 2O(n)nn2 by Hanrot and Stehlé in 2007. Using their point-counting method, the constant hidden in “O(n)O(n)” is strictly bigger than 1.9. In this paper, we give a new counting method which we call “sequence counting” method to bound the number of loop iterations and show that the time complexity is actually upper bounded by 20.401n+o(n)⋅nn2.