New Generic Algorithms for Hard Knapsacks

摘要

In this paper, we study the complexity of solving hard knapsack problems, i.e., knapsacks with a density close to 1 where lattice-based low density attacks are not an option. For such knapsacks, the current state-of-the-art is a 31-year old algorithm by Schroeppel and Shamir which is based on birthday paradox techniques and yields a running time of O(2~(n/2)) for knapsacks of n elements and uses O(2~(n/4)) storage. We propose here two new algorithms which improve on this bound, finally lowering the running time down to either O(2~(0.385n)) or O(2~(0.3113n)) under a reasonable heuristic. We also demonstrate the practicality of these algorithms with an implementation.