Welcome to the resource topic for 2010/189
Title:
New generic algorithms for hard knapsacks
Authors: Nick Howgrave-Graham, Antoine Joux
Abstract: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 \TildeOh(2^{n/2}) for knapsacks of n elements and uses \TildeOh(2^{n/4}) storage. We propose here two new algorithms which improve on this bound, finally lowering the running time down to \TildeOh (2^{0.3113\, n}) for almost all knapsacks of density 1. We also demonstrate the practicality of these algorithms with an implementation.
ePrint: https://eprint.iacr.org/2010/189
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .