Better Sample -- Random Subset Sum in $2^{0.255n}$ and its Impact on Decoding Random Linear Codes
This work addresses cryptographic security and coding theory by providing faster algorithms for subset sum and code decoding, though it is incremental as it builds on prior methods like HGJ and BCJ.
The paper tackles the problem of solving random subset sum instances, a key cryptographic task, by proposing a new heuristic algorithm that reduces the run time from 2^{0.291n} to 2^{0.255n}. It also applies this algorithm to decoding random binary linear codes, improving the run time from 2^{0.048n} to 2^{0.042n} in the half distance decoding setting.
We propose a new heuristic algorithm for solving random subset sum instances $a_1, \ldots, a_n, t \in \mathbb{Z}_{2^n}$, which play a crucial role in cryptographic constructions. Our algorithm is search tree-based and solves the instances in a divide-and-conquer method using the representation method. From a high level perspective, our algorithm is similar to the algorithm of Howgrave-Graham-Joux (HGJ) and Becker-Coron-Joux (BCJ), but instead of enumerating the initial lists we sample candidate solutions. So whereas HGJ and BCJ are based on combinatorics, our analysis is stochastic. Our sampling technique introduces variance that increases the amount of representations and gives our algorithm more optimization flexibility. This results in the remarkable and natural property that we improve with increasing search tree depth. Whereas BCJ achieves the currently best known (heuristic) run time $2^{0.291n}$ for random subset sum, we improve (heuristically) down to $2^{0.255n}$ using a search tree of depth at least $13$. We also apply our subset algorithm to the decoding of random binary linear codes, where we improve the best known run time of the Becker-Joux-May-Meurer algorithm from $2^{0.048n}$ in the half distance decoding setting down to $2^{0.042n}$.