**Solving Subset Sum Problems of Densioty close to 1 by "randomized" BKZ-reduction**

*Claus P. Schnorr and Taras Shevchenko*

**Abstract: **Subset sum or Knapsack problems of dimension $n$ are known to be hardest for knapsacks of density close to 1.These problems are NP-hard for arbitrary $n$. One can solve such problems either by lattice basis reduction or by optimized birthday algorithms. Recently Becker, Coron, Jou } [BCJ10] present a birthday algorithm that
follows Schroeppel, Shamir [SS81], and Howgrave-Graham, Joux [HJ10]. This algorithm solves 50 random knapsacks of dimension 80 and density close to 1 in roughly 15 hours on a 2.67 GHz PC.
We present an optimized lattice basis reduction algorithm that follows Schnorr, Euchne} [SE03] using pruning of Schnorr, H\"orner [SH95] that solves such random knapsacks of dimension 80 on average in less than a minute, and 50 such problems all together about 9.4 times faster and using much less space than [BCJ10] on another 2.67 GHz PC.

**Category / Keywords: **foundations / BKZ, block reduction of lattice bases, subset sum problem

**Date: **received 2 Nov 2012

**Contact author: **scjhnorr at cs uni-frankfurt de

**Available format(s): **PDF | BibTeX Citation

**Version: **20121105:134035 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]