Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/20476
Title: | Lattice Basis Reduction Algorithms and the Subset Sum Problem |
Authors: | Bo, Yang |
Advisor: | Qiao, Sanzheng |
Department: | Computing and Software |
Publication Date: | 2016 |
Abstract: | It is well-known that the subset sum problem is NP-complete, which is the basis for the subset sum based public-key cryptosystems. Some attacks on such cryptosystems have been developed. Those methods reduce the subset sum problem to the problem of finding a shortest Euclidean-norm nonzero vector in a point lattice. In this thesis, we propose a new hybrid lattice basis reduction algorithm by integrating the recent polynomial time Type-I reduction algorithm by Wen Zhang in 2015 with other techniques. We show that our algorithm is well suited for high dimensional lattices and apply it to the subset sum problem. Our experiments demonstrate that our method can solve certain types of the subset sum problems with higher success rates than the most famous existing methods, the Lagarias-Odlyzko attack and the Radziszowski-Kreher attack. |
URI: | http://hdl.handle.net/11375/20476 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Bo_Yang_201608_MasterofComputerScience.pdf | 978.63 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.