Given positive integers $a_1,..., a_n, t$, the fixed weight subset sum problem is to find a subset of the $a_i$ that sum to $t$, where the subset has a prescribed number of elements. It is this problem that underlies the security of modern knapsack cryptosystems, and solving the problem results directly in a message attack. We present new exponential algorithms that do not rely on lattices, and hence will be applicable when lattice basis reduction algorithms fail. These algorithms rely on a generalization of the notion of splitting system given by Stinson. In particular, if the problem has length $n$ and weight $\ell$ then for constant $k$ a power of two less than $n$ we apply a $k$-set birthday algorithm to the splitting system of the problem. This randomized algorithm has time and space complexity that satisfies $T \cdot S^{\log{k}} = O({n \choose \ell})$ (where the constant depends uniformly on $k$). In addition to using space efficiently, the algorithm is highly parallelizable.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok