AbstractsComputer Science

A Verifiable Payment Mechanism with Privacy-Preserving in Smart Grid

by Yu-Lun Chuang

Institution: NSYSU
Year: 2016
Keywords: Lattice; Algorithm Analysis; Optimization Theory; Lattice-Based Cryptography; Shortest Vector Problem
Posted: 02/05/2017
Record ID: 2100973
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).