Welcome to the resource topic for 2022/1329
Title:
New Time-Memory Trade-Offs for Subset Sum – Improving ISD in Theory and Practice
Authors: Andre Esser, Floyd Zweydinger
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.
ePrint: https://eprint.iacr.org/2022/1329
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .