About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
Blockchain Technology and Emerging Applications. Third EAI International Conference, BlockTEA 2023, Wuhan, China, December 2-3, 2023, Proceedings

Research Article

A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)

Cite
BibTeX Plain Text
  • @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
Errui He1, Tianyu Xu1, Mengsi Wu1, Jiageng Chen1, Shixiong Yao1, Pei Li1,*
  • 1: Central China Normal University, Wuhan
*Contact email: peili@ccnu.edu.cn

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.

Keywords
Lattice reduction LLL BKZ Enumeration Sieving Parallel computing
Published
2024-05-03
Appears in
SpringerLink
http://dx.doi.org/10.1007/978-3-031-60037-1_4
Copyright © 2023–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL