You are looking at a specific version 20100409:150331 of this paper. See the latest version.

Paper 2010/189

New generic algorithms for hard knapsacks

Nick Howgrave-Graham and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Long version of Eurocrypt 2010 article
Keywords
knapsack problemrandomized algorithm
Contact author(s)
Antoine Joux @ m4x org
History
2010-04-09: received
Short URL
https://ia.cr/2010/189
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.