A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)
摘要
Lattice-based encryption schemes derive their security from the presumed complexity of solving the Shortest Vector Problem (SVP) within the lattice structure. Numerous algorithms have been proposed to address the SVP, targeting both exact and approximate solutions. However, it is noteworthy that the time complexity associated with these algorithms predominantly exceeds polynomial bounds. This paper succinctly delineates these algorithms while providing a comprehensive summary of existing parallel implementations of sieving and enumeration methods. Furthermore, it introduces distinguished instances from the Hall of Fame of the SVP challenge.