[HGJ10] New Generic Algorithms for Hard Knapsacks

Authors: Nick Howgrave-Graham, Antoine Joux | Venue: EUROCRYPT 2010 | Source

Abstract

In this paper, we study the complexity of solving hard knapsack problems, i.e., knapsacks with a density close to 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 for knapsacks of elements and uses storage. We propose here two new algorithms which improve on this bound, finally lowering the running time down to for almost all knapsacks of density . We also demonstrate the practicality of these algorithms with an implementation.

BibTeX

@Inproceedings{EC:HowJou10,
  author = {Nick {Howgrave-Graham} and Antoine Joux},
  title = {New Generic Algorithms for Hard Knapsacks},
  pages = {235--256},
  editor = {Henri Gilbert},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2010},
  volume = {6110},
  series = {Lecture Notes in Computer Science},
  address = {French Riviera},
  month = {may~30~--~jun~3},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2010},
  doi = {10.1007/978-3-642-13190-5_12},
}