|Keywords:||Lattice; Algorithm Analysis; Optimization Theory; Lattice-Based Cryptography; Shortest Vector Problem|
|Full text PDF:||http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0729116-132326|
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. SVP is an NP-hard problem 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 thesis, we propose a new SVP algorithm which can be performed in time complexity O(n3). We also prove that the Hermite factor of the proposed algorithm is polynomial-bounded. Advisors/Committee Members: Ray-Lin Tso (chair), I-Te Chen (chair), Chun-I Fan (committee member), Wen-Sheng Juang (chair), Chun-Yuan Hsiao (chair).