Paper 2022/1329

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

Andre Esser, Technology Innovation Institute
Floyd Zweydinger, Ruhr University Bochum

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 for an exponentially small success probability. We compensate for this reduced probability by multiple randomized executions. Our main improvement stems from the clever reuse of parts of the computation in subsequent executions to reduce the time complexity per iteration. As an application of our construction, we derive the first non-trivial time-memory trade-offs for Information Set Decoding (ISD) algorithms. Our new algorithms improve on previous (implicit) trade-offs asymptotically as well as practically. Moreover, our optimized implementation also improves on running time, due to reduced memory access costs. We demonstrate this by obtaining a new record computation in decoding quasi-cyclic codes (QC-3138). Using our newly obtained data points we then extrapolate the hardness of suggested parameter sets for the NIST PQC fourth round candidates McEliece, BIKE and HQC, lowering previous estimates by up to 6 bits and further increasing their reliability.

Available format(s)
Attacks and cryptanalysis
Publication info
representation technique information set decoding code-based cryptography record computation security estimates
Contact author(s)
andre r esser @ gmail com
floyd zweydinger @ rub de
2022-10-10: approved
2022-10-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andre Esser and Floyd Zweydinger},
      title = {New Time-Memory Trade-Offs for Subset Sum -- Improving ISD in Theory and Practice},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1329},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.