International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: New generic algorithms for hard knapsacks

Authors:
Nick Howgrave-Graham
Antoine Joux
Download:
URL: http://eprint.iacr.org/2010/189
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23090,
  title={New generic algorithms for hard knapsacks},
  booktitle={IACR Eprint archive},
  keywords={foundations / knapsack problem, randomized algorithm},
  url={http://eprint.iacr.org/2010/189},
  note={Long version of Eurocrypt 2010 article Antoine.Joux@m4x.org 14705 received 6 Apr 2010},
  author={Nick Howgrave-Graham and Antoine Joux},
  year=2010
}