Lattice Basis Reduction Algorithms and the Subset Sum Problem

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.