Paper 2011/474 Original: eprint.iacr.org/2011/474 ↗
Improved Generic Algorithms for Hard Knapsacks
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2011-09-06: last updated
- 2011-09-06: published
- Short URL
- https://ia.cr/2011/474
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2011/474,
author = {Anja Becker and Jean-Sébastien Coron and Antoine Joux},
title = {Improved Generic Algorithms for Hard Knapsacks},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/474},
year = {2011},
url = {https://eprint.iacr.org/2011/474}
}