A Survey on Classical Lattice Algorithms

The rapid advancement of quantum computing poses a severe threat to traditional public key cryptosystems. Lattice-based cryptography has emerged as a core candidate for post-quantum cryptography due to its presumed quantum resistance, robust security foundations, and functional versatility, with its concrete security relying on the computational hardness of lattice problems. Existing lattice-based cryptography surveys mainly focus on cryptosystem design, scheme comparisons, and post-quantum cryptography standardization progress, with only cursory coverage of classical lattice algorithms that underpin the concrete security of lattice-based cryptography. We present the first systematic survey of classical lattice algorithms, focusing on two core categories of algorithms for solving lattice problems: approximate algorithms and exact algorithms. The approximate algorithms cover mainstream lattice basis reduction methods such as Lenstra–Lenstra–Lovász (LLL), Block Korkine–Zolotarev (BKZ), and General Sieve Kernel (G6K) algorithms, as well as alternative frameworks. The exact algorithms encompass dominant techniques like enumeration and sieving algorithms, along with alternative strategies. We systematically trace the evolutionary trajectory and inherent logical connections of various algorithms, clarify their core mechanisms, and identify promising future research directions. This survey not only serves as an introductory guide for beginners but also provides a valuable reference for seasoned researchers, facilitating the concrete security evaluation of lattice-based cryptosystems and the design of novel lattice algorithms.