Paper 2010/189 Original: eprint.iacr.org/2010/189 ↗
New generic algorithms for hard knapsacks
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
- Preprint.
- History
- 2010-04-09: last updated
- 2010-04-09: published
- Short URL
- https://ia.cr/2010/189
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2010/189,
author = {Nick Howgrave-Graham and Antoine Joux},
title = {New generic algorithms for hard knapsacks},
howpublished = {Cryptology {ePrint} Archive, Paper 2010/189},
year = {2010},
url = {https://eprint.iacr.org/2010/189}
}