| URN |
etd-0729116-132326 |
|---|
| Author |
Yu-Lun Chuang |
|---|
| Author's Email Address |
No Public. |
|---|
| Statistics |
This thesis had been viewed 5589 times. Download 145 times. |
|---|
| Department |
Computer Science and Engineering |
|---|
| Year |
2015 |
|---|
| Semester |
2 |
|---|
| Degree |
Master |
|---|
| Type of Document |
|
|---|
| Language |
English |
|---|
| Title |
An Efficient Algorithm for the Shortest Vector Problem. |
|---|
| Date of Defense |
2016-07-05 |
|---|
| Page Count |
45 |
|---|
| Keyword |
Lattice
Algorithm Analysis
Optimization Theory
Lattice-Based Cryptography
Shortest Vector Problem
|
|---|
| Abstract |
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(n^3). We also prove that the Hermite factor of the proposed algorithm is polynomial-bounded. |
|---|
| Advisory Committee |
Wen-Sheng Juang - chair
Ray-Lin Tso - co-chair
Chun-Yuan Hsiao - co-chair
I-Te Chen - co-chair
Chun-I Fan - advisor
|
|---|
| Files |
Indicate in-campus at 2 year and off-campus access at 2 year. |
|---|
| Date of Submission |
2016-08-29 |
|---|
