Introduction

In the previous chapter we discussed the theoretical and empirical implications of Seysen's basis reduction algorithm. As Chapter 1 pointed out, many problems in discrete mathematics may be reduced to problems involving lattices and basis reduction. In this chapter we use Seysen's algorithm to solve subset sum problems. The subset sum problem in the general case is NP-complete, and many knapsack-type cryptosystems have been suggested which depend on the difficulty of solving subset sum problems. We show below that Seysen's algorithm, when used in conjunction with the LLL algorithm and other techniques, allows us to solve a large class of subset sum problems in polynomial time. We begin our analysis with the definition of a subset sum problem.

Definition.   Let $A=\{a_1,\ldots{},a_n\}$ be a set of positive integers (the weights). Let $A' \subset A$ be some subset of A, and let s be the sum of the elements of A'. Then

$$s = \sum_{i=1}^n e_ia_i, \quad\text{for } e_i \in \{0,1\}, 1 \leq i \leq n.$$ (3.1)

The subset sum or knapsack problem is to find, given the set A of weights and the sum s, some subset A' of A. Equivalently, one may find a set of values for the 0-1 variables $e_1,\ldots{},e_n$, where e_i = 1 if and only if $a_i \in A'$.

The subset sum problem is known to be NP-complete [15]. In the INSTANCE-QUESTION format often used to phrase NP-complete decision problems, the subset sum decision problem would be described as follows:

INSTANCE A set of positive integers $A=\{a_1,\ldots{},a_n\}$ and an integer s.
QUESTION Does there exist a subset A' of A such that the sum of the elements of A' is s?

Clearly, if we can solve subset sum problems in polynomial time, we can answer the subset sum decision problem in polynomial time. The converse is also true; we can ask an oracle which answers the subset sum decision problem in polynomial time whether there is a solution to the subset sum problem with weights $a_2,\ldots{},a_n$ and sum s-a₁. If there is such a solution, then there exists a solution to the original problem that included a₁ (i.e. we can set e₁ = 1). If the oracle say no such solution exists, then a₁ cannot be in the subset which sums to s, and we know that e₁ = 0. We can then recurse and determine $e_2,e_3,\ldots{},e_n$ in sequence. Many public-key cryptosystems have been proposed with the difficulty of solving subset sum problems as the basis for their security. (See [7,8,13,31] for surveys of this field.) Almost all of these cryptosystems have been shown to be insecure; the Chor-Rivest one [11] is perhaps the most widely known system which has not yet been broken. The majority of the attacks on knapsack-based cryptosystems have involved discovering the secret information hidden in the weights which allows the receiver A to decrypt the message quickly. However, there have been two independent attacks, one due to Brickell [6] and one due to Lagarias and Odlyzko [26], which attempt to solve all subset sum problems of a certain type, independent of the method in which the weights were chosen. These methods (and the newer result in [12]) depend in theory only on the density of the subset sum problem to be solved. In practice, however, the success rate of these methods is bounded by the performance of the basis reduction technique used in the attack. Section 3.2 below outlines currently known methods for solving subset sum problems, and describes a new method which significantly increases the class of problems which may be attacked in practice. Section 3.3 discusses current methods for actually solving a specific subset sum problem, and the limits of these methods. In Section 3.4 we show how to use Seysen's algorithm in conjunction with multiple versions of the LLL algorithm and other heuristics to solve a larger class of subset sum problems. Section 3.5 presents empirical results obtained by solving a large number of subset sum problems using Seysen's algorithm. These results give experimental evidence that it is possible to solve a much larger class of subset sum problems in polynomial time than was previously thought possible.