[BCJ11] Improved Generic Algorithms for Hard Knapsacks

Authors: Anja Becker, Jean-Sébastien Coron, Antoine Joux | Venue: EUROCRYPT 2011 | Source

Abstract

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time O(2^0.337n) and memory O(2^0.256n), thereby improving a 30-year old algorithm by Shamir and Schroeppel. In this paper we extend the Howgrave-Graham Joux technique to get an algorithm with running time down to O(2^0.291n). An implementation shows the practicability of the technique. Another challenge is to reduce the memory requirement. We describe a constant memory algorithm based on cycle finding with running time O(2^0.72n); we also show a time-memory tradeoff.

BibTeX

@Inproceedings{EC:BecCorJou11,
  author = {Anja Becker and Jean-S{\'e}bastien Coron and Antoine Joux},
  title = {Improved Generic Algorithms for Hard Knapsacks},
  pages = {364--385},
  editor = {Kenneth G. Paterson},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2011},
  volume = {6632},
  series = {Lecture Notes in Computer Science},
  address = {Tallinn, Estonia},
  month = {may~15--19},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2011},
  doi = {10.1007/978-3-642-20465-4_21},
}