Title page for etd-0729116-132326


[Back to Results | New Search]

URN etd-0729116-132326
Author Yu-Lun Chuang
Author's Email Address No Public.
Statistics This thesis had been viewed 5338 times. Download 15 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
  • etd-0729116-132326.pdf
  • Indicate in-campus at 2 year and off-campus access at 2 year.
    Date of Submission 2016-08-29

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys