Discussion

The analysis above shows that it is possible to improve the density bound from $0.6463\ldots{}$ to $0.9408\ldots{}$ by modifying one vector in the lattice basis. We now consider the possibilities of improving on this bound.

Solving subset sum problems with basis reduction is closely connected to lattice covering problems. In particular, we want to cover the vertices of the n-cube (representing the possible e solution vectors) with a polynomial number of n-spheres of radius $\sqrt{\alpha n}$. Lagarias and Odlyzko showed that it was possible to cover the n-cube with two n-spheres of radius $\sqrt{\tfrac{1}{2}n}$. The two spheres (centered at $(0,0,\ldots{},0)$ and $(1,1,\ldots{},1)$) correspond to the two basis reduction problems which must be solved for any given subset sum problem. Our analysis above uses one n-sphere of radius $\tfrac{1}{2}\sqrt{n}$ centered at $(\tfrac{1}{2},\tfrac{1}{2},\ldots{},\tfrac{1}{2})$ to cover all the points.

One way to improve the bound presented above would be to show that it is possible to cover the vertices of the n-cube with a polynomial number of n-spheres of radius $\sqrt{\alpha n}$ with $\alpha < \tfrac{1}{4}$. We show that this is not possible, and that the asymptotic bound of $0.9408\ldots{}$ cannot be improved in this way. The following proposition shows that any n-sphere of radius $\sqrt{\alpha n}$ with $\alpha < \tfrac{1}{4}$ can cover only an exponentially small fraction of the vertices of the n-cube. Thus, no polynomial collection of such spheres can satisfy our requirements.

Proposition.   Any sphere of radius $\sqrt{\alpha n}, \alpha < \tfrac{1}{4}$, in ${\mathbb R}^{{n}}$ contains at most $(2~-~\delta)^n$ points of $\{0,1\}^n$, for some $\delta = \delta(\alpha) > 0$.

Proof. Suppose that the n-sphere is centered at the point $\mathbf{c}=(c_1,\ldots{},c_n)$. We are interested in the number of points $\mathbf{e} \in \{0,1\}^n$ for which $\Vert\mathbf{c}-\mathbf{e}\Vert^2 \leq \alpha n$. Using the upper bound technique of [15], we show that N, the number of points in $\{0,1\}^n$ inside the sphere, is bounded by

$$N \leq e^{\alpha n}\prod_{i=1}^n (e^{-c_i^2} + e^{-(c_i-1)^2}).$$ (16)

If the point $\mathbf{e}=(e_1,\ldots{},e_n)$ is inside the sphere, then $\Vert\mathbf{c}-\mathbf{e}\Vert^2 = \sum_{i=1}^n (c_i-e_i)^2 \leq \alpha n$, and after expanding the right side, Equation 20 contains a term of the form

$$\exp\left(\alpha n- \sum_{i=1}^n (c_i-e_i)^2\right) \geq 1,$$

for each such point e, which proves Equation 20 since all terms in the expansion are nonnegative.

Since the terms in the product in Equation 20 are independent, we know that the value of N is bounded by

$$e^{\alpha n} \max_{\mathbf{c} \in {\mathbb R}^{{n}}} \prod_{i... ..._i^2} + e^{-(c_i-1)^2}\right) \leq e^{\alpha n} (2e^{-1/4})^n.$$

(It is easy to show that the maximum value of f(z)=e^-z2 + e^-(z-1)2 is 2e^-1/4.) Thus,
$$\begin{align*}N \leq e^{n \alpha} 2^n e^{(-1/4)n} &= 2^n e^{n(\alpha - 1/4)} \\ ... ...alpha))^n, \quad\text{for } \delta(\alpha) = 2(1-e^{\alpha - 1/4}) \end{align*}$$
For all $\alpha < \tfrac{1}{4}$, $\delta(\alpha) > 0$, which proves the proposition.    $\blacksquare$

As $n\rightarrow \infty$, any n-sphere with radius $\sqrt{\alpha n}$, $\alpha < \tfrac{1}{4}$, will contain at most $(2~-~\delta(\alpha))^n$points in $\{0,1\}^n$. Thus, any polynomial-sized collection of spheres cannot contain all the points in $\{0,1\}^n$. Thus we cannot hope to asymptotically improve the $0.9408\ldots{}$ bound by reducing a polynomial number of bases with different b_n+1 vectors. However, for small dimensions it might be possible to improve the bound, even though any such advantage will disappear as n grows.

In cases where the subset sum problem (Equation 1) to be solved is known to have $\sum \, e_i$ small (as occurs in some knapsack cryptosystems, such as the Chor-Rivest one [4], which has still not been broken), it is possible to again improve on the results of [12] by our approach. For example, if we know that

$$\sum_{i=1}^{n} e_i = \beta n,$$

we can replace the vector b_n+1 in the basis of L by

$$\mathbf{b_{n+1}''} = (\beta,\beta,\ldots,\beta,Ns),$$

and then the lattice L will contain a vector of length $\sqrt{n \beta(1-\beta)}$, and our analysis shows that in this case it then becomes possible to solve most problems with even smaller weights a_i. However, it appears that there are choices for parameters in the Chor-Rivest knapsack that would resist even this attack.

When we consider the $L_{\infty}$ or sup-norm,

$$\Vert(x_1,\ldots,x_n ) \Vert _{\infty} = \max_{1 \leq j \leq n} \vert x_j\vert,$$

then we find that the vector $\mathbf{\hat{e}'}$ has norm 1/2. Since there are at most 2ⁿ non-zero vectors in L' of norm $\leq 1/2$, we can solve almost all subset sum problems of any density < 1 if we have a lattice oracle for the sup-norm. Formally, we may make the following proposition:

Proposition.   Let A be a positive integer, and let $a_1,\ldots{},a_n$ be random integers with $0 < a_i \leq A$ for $1 \leq i \leq n$. Let $\mathbf{e}=(e_1,\ldots{},e_n) \in \{0,1\}^n$ be arbitrary, and let $s = \sum_{i=1}^n e_ia_i$. If the density d < 1, then the subset sum problem defined by $a_1,\ldots{},a_n$ and s may ``almost always'' be solved in polynomial time, given the existence of a sup-norm lattice oracle.

The general sup-norm shortest vector problem is known to be NP-complete [6]; the complexity of the square-norm shortest vector problem is an open problem. That a sup-norm lattice oracle yields a better density bound than a square-norm lattice oracle suggests that the shortest vector problem for the sup-norm might be harder than for the square-norm.

 

Table: $\parbox{5in}{Fraction of random subset sum problems solved by a particular reduction algorithm applied to bases <I>L</I> and <I>L</I>', respectively}$

n	b	L	L'
50	50	0.05	1.00
50	60	0.55	1.00
50	75	1.00	-
66	76	-	0.25
66	84	-	0.80
66	92	-	0.95
66	100	-	1.00
66	104	0.30	1.00
66	108	0.55	1.00
66	112	0.60	1.00
66	116	1.00	-

Sections 3 and 4 presented theoretical results that assume the availability of an efficient method for finding the shortest non-zero vector in a lattice. When one uses known algorithms for lattice basis reduction, applying them to lattice L' instead of lattice L also yields dramatic improvements, although the results are not as good as they would be in the presence of a lattice oracle. For example, Table 1 presents the comparison obtained in one particular set of experiments. The lattices used were not exactly L and L', and the reduction algorithm used a combination of ideas from several sources. More extensive data sets and details of the computations are presented in [13]. For each entry in Table 1, n denotes the number of items, and b the number of bits (chosen at random) for each item. For each (n,b) combination, 20 problems were attempted, where in each case e_i =1 for exactly n/2 of the items. The entries for the L and L'column indicate what fraction of the 20 problems were solved in each case. Combining the improved lattice of this paper with variants of the algorithms of [19] leads to solutions of subset sum problems of even higher densities, as is shown in [21].