Research Article
A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)
@INPROCEEDINGS{10.1007/978-3-031-60037-1_4, author={Errui He and Tianyu Xu and Mengsi Wu and Jiageng Chen and Shixiong Yao and Pei Li}, title={A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)}, proceedings={Blockchain Technology and Emerging Applications. Third EAI International Conference, BlockTEA 2023, Wuhan, China, December 2-3, 2023, Proceedings}, proceedings_a={BLOCKTEA}, year={2024}, month={5}, keywords={Lattice reduction LLL BKZ Enumeration Sieving Parallel computing}, doi={10.1007/978-3-031-60037-1_4} }- Errui He
Tianyu Xu
Mengsi Wu
Jiageng Chen
Shixiong Yao
Pei Li
Year: 2024
A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)
BLOCKTEA
Springer
DOI: 10.1007/978-3-031-60037-1_4
Abstract
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.
Copyright © 2023–2025 ICST
