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

##### Abstract

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)
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
representation technique information set decoding code-based cryptography record computation security estimates
Contact author(s)
andre r esser @ gmail com
floyd zweydinger @ rub de
History
2022-10-10: approved
See all versions
Short URL
https://ia.cr/2022/1329

CC BY

BibTeX

@misc{cryptoeprint:2022/1329,
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{https://eprint.iacr.org/2022/1329}},
url = {https://eprint.iacr.org/2022/1329}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.