Introduction

The knapsack or subset sum problem is to find, given positive integers $a_1,\ldots{},a_n$ (the weights) and s, some subset of the a_i that sum to s, or equivalently to find variables $e_1,\ldots{},e_n$, with $e_i \in \{0,1\}$, such that

$$\sum_{i=1}^n e_ia_i = s.$$ (1)

This problem is known to be NP-complete [9] (in its feasibility recognition form), and so is thought to be very hard in general. This has led to the invention of several public-key cryptosystems based on the knapsack problem. Almost all of these have been broken by now, however. (See [2,3,5,16] for surveys of this field.) Most of the attacks exploited specific constructions of the relevant cryptosystems. In addition, two algorithms have been proposed, one by Brickell [1] and the other by Lagarias and Odlyzko [12] which show that almost all low-density subset sum problems can be solved in polynomial time. The density of a set of weights $a_1,\ldots{},a_n$ is defined by

$$d = \frac{n}{{\displaystyle \log_2 \max\begin{substack}1 \leq i \leq n\end{substack}a_i}}.$$ (2)

The interesting case is $d \leq 1$, since for d > 1 there will in general be many subsets of weights with the same sum, and so such sets of weights could not be used for transmitting information. The Brickell and Lagarias-Odlyzko algorithms solve almost all subset sum problems with d sufficiently small.

Both the Brickell and Lagarias-Odlyzko algorithms reduce the subset sum problem to that of finding a short vector in a lattice. The exact complexity of finding short vectors in lattices is not known, and expert opinion appears to be divided as to whether this problem is polynomial or not. At the moment, the best known polynomial time method in this area is the L³ lattice basis reduction algorithm of Lenstra, Lenstra, and Lovász [14], which is only guaranteed to find a non-zero vector in an n-dimensional lattice that is at most an exponential times the length of the shortest non-zero vector in that lattice. If one uses that algorithm, the Lagarias-Odlyzko method can be shown rigorously to solve almost all subset sum problems of density < c/nfor large n and for a fixed constant c, as is done in [12]. (See [7] for a simplified analysis of the algorithm.) Using more recent algorithms of Schnorr [20], one can improve the cutoff bound to c' /n for arbitrarily small constants c' > 0, but at the cost of increasing the degree of the polynomial that bounds the running time.

Finding short vectors in lattices may be very hard in general. On the other hand, published algorithms, such as the L³ one, perform much better in practice than is guaranteed by their worst case bounds, especially when they are modified [12,13,18], and new algorithms are being invented [19,20,22]. Thus it is possible that on average, the problem of finding short vectors in lattices is easy, even if it is hard in the worst case. Therefore it seems worthwhile to separate the issues of efficiency of lattice basis reduction algorithms from the question of how well the subset sum problem can be reduced to that of finding a short vector in a lattice. (Note that Paz and Schnorr [17] have shown that the general problem of finding the shortest non-zero vector in a lattice is reducible to that of solving some subset sum problem, but with some loss of efficiency.)

Consider a lattice oracle that, given a basis for a lattice, with high probability yields in polynomial time the shortest non-zero vector in that lattice. We do not know how to construct such an oracle, but it might be possible to do so, and in any case in relatively low dimensions, known polynomial time algorithms act like such an oracle. The analysis of [12] showed that availability of such an oracle would let the Lagarias-Odlyzko algorithm solve almost all subset sum problems of density $< 0.6463\ldots{}$, but not higher than that. (Similar analyses are not available for the Brickell algorithm [1], although it seems to require even lower densities. See also [8].)

In this note we analyze a simple modification of the part of the Lagarias-Odlyzko algorithm that reduces the subset sum problem to a short vector in a lattice problem. We show that with this modification, a single call to a lattice oracle would lead to polynomial time solutions of almost all problems of density $< 0.9408\ldots{}$. Empirical tests show that this modification also leads to dramatic improvement in the performance of practical algorithms. We present some results on this in Section 4. More data and fuller comparisons will be given in [13].

In Section 2 we derive the Lagarias-Odlyzko bound using the approach in [7]. We show in Section 3 that this bound may be increased to $0.9408\ldots{}$ using a simple modification of the Lagarias-Odlyzko attack. Finally, Section 4 discusses possible improvements on the new bound and practical results.

Joux and Stern [11] have found another modification of the Lagarias-Odlyzko algorithm. While the lattice they use is very different from ours, they obtain the same $0.9408\ldots{}$ density bound.