An Efficient Algorithm for the Shortest Vector Problem

作者：Chuang, Yu Lun; Fan, Chun , I^*; Tseng, Yi Fan

来源：IEEE Access, 2018, 6: 61478-61487.

DOI：10.1109/ACCESS.2018.2876401

• Shortest vector problem
• algorithm analysis
• optimization theory
• lattice
• lattice-based cryptography

Lattice is widely used in cryptography since it has potential for defending quantum attacks. One of the significant problems in such cryptography is the shortest vector problem (SVP). This problem is to find the non-zero shortest vector in lattice. The SVP is an NP-hard problem under randomized reductions proven by Ajtai, and many cryptosystems are secure under the assumption that SVP is hard, such as NTRU. On the other hand, some primitives of lattice-based cryptography require relatively short vectors. In this paper, we propose a new SVP algorithm that can be performed in time complexity O(n(3)). We also prove that the Hermite factor of the proposed algorithm is polynomial-bounded.

• 出版日期2018
• 单位中山大学