** Next:** Point Lattices
** Up:** No Title
** Previous:** List of Figures

#

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.

*Brian A. LaMacchia*

*1999-10-30*