New Time-Memory Trade-Offs for Subset Sum -- Improving ISD in Theory and Practice

ePrint Report: New Time-Memory Trade-Offs for Subset Sum -- Improving ISD in Theory and Practice

Andre Esser, Floyd Zweydinger

We propose new time-memory trade-offs for the random subset sum problem defined on $(a_1,\ldots,a_n,t)$ over $\mathbb{Z}_{2^n}$.


Our trade-offs yield significant running time improvements for every fixed memory limit $M\geq2^{0.091n}$. Furthermore, we interpolate to the running times of the fastest known algorithms when memory is not limited.
Technically, our design introduces a pruning strategy to the construction by Becker-Coron-Joux (BCJ) that allows …

eprint report memory practice theory trade