Introduction

In 1985 Lagarias and Odlyzko [26] developed a general attack on knapsack cryptosystems which reduces solving subset sum problems to the problem of finding the Euclidean-norm shortest nonzero vector in a point lattice. Recent improvements to this attack [12,19] have stimulated interest in finding lattice basis reduction algorithms well-suited to the lattices associated with subset sum problems. This thesis studies a new approach to lattice basis reduction originally developed by M. Seysen [38]. Seysen's reduction algorithm was initially developed to find simultaneously good bases of a lattice and its dual lattice. However, it may also be successfully applied to solving subset sum problems, especially when combined with other known reduction methods. Using a collection of techniques, including Seysen's algorithm, we show that it is possible to solve in practice a much larger class of subset sum problems than was previously possible.