The paper presents a comprehensive survey of closest-point search methods for lattices without a regular structure. It describes existing search strategies in a unified framework and highlights their differences. An efficient closest-point search algorithm based on the Schnorr-Euchner variation of the Pohst method is implemented. Given an arbitrary point x in R^m and a generator matrix for a lattice Λ, the algorithm computes the point of Λ closest to x. The algorithm is shown to be substantially faster than other known methods, as demonstrated by theoretical comparisons with the Kannan algorithm and experimental comparisons with the Pohst algorithm and its variants. Modifications of the algorithm are developed to solve related search problems for lattices, such as finding the shortest vector, determining the kissing number, computing Voronoi-relevant vectors, and finding a Korkine-Zolotareff reduced basis.
The paper discusses the closest-point problem, which involves finding the lattice point closest to a given input point. The Voronoi region of a lattice point is the set of all vectors in R^m that can be decoded to this point. The Voronoi diagram of a lattice is the set of all its Voronoi regions. The paper also discusses the shortest-vector problem, which involves finding the shortest non-zero vector in a lattice. The paper highlights the importance of lattice basis reduction in cryptography and discusses various lattice search algorithms, including the Pohst strategy, the Kannan strategy, and the Schnorr-Euchner refinement of the Pohst strategy. The paper presents a detailed pseudo-code implementation of a closest-point search algorithm based on the Schnorr-Euchner strategy. It also discusses preprocessing and postprocessing techniques to improve the efficiency of the algorithm. The paper concludes with a complexity analysis of the closest-point algorithm and compares it with the Kannan algorithm. The paper also discusses other lattice search problems, including the shortest-vector problem, the kissing number, and the Voronoi-relevant vectors.The paper presents a comprehensive survey of closest-point search methods for lattices without a regular structure. It describes existing search strategies in a unified framework and highlights their differences. An efficient closest-point search algorithm based on the Schnorr-Euchner variation of the Pohst method is implemented. Given an arbitrary point x in R^m and a generator matrix for a lattice Λ, the algorithm computes the point of Λ closest to x. The algorithm is shown to be substantially faster than other known methods, as demonstrated by theoretical comparisons with the Kannan algorithm and experimental comparisons with the Pohst algorithm and its variants. Modifications of the algorithm are developed to solve related search problems for lattices, such as finding the shortest vector, determining the kissing number, computing Voronoi-relevant vectors, and finding a Korkine-Zolotareff reduced basis.
The paper discusses the closest-point problem, which involves finding the lattice point closest to a given input point. The Voronoi region of a lattice point is the set of all vectors in R^m that can be decoded to this point. The Voronoi diagram of a lattice is the set of all its Voronoi regions. The paper also discusses the shortest-vector problem, which involves finding the shortest non-zero vector in a lattice. The paper highlights the importance of lattice basis reduction in cryptography and discusses various lattice search algorithms, including the Pohst strategy, the Kannan strategy, and the Schnorr-Euchner refinement of the Pohst strategy. The paper presents a detailed pseudo-code implementation of a closest-point search algorithm based on the Schnorr-Euchner strategy. It also discusses preprocessing and postprocessing techniques to improve the efficiency of the algorithm. The paper concludes with a complexity analysis of the closest-point algorithm and compares it with the Kannan algorithm. The paper also discusses other lattice search problems, including the shortest-vector problem, the kissing number, and the Voronoi-relevant vectors.