Better Sample -- Random Subset Sum in 2^0.255n and its Impact on Decoding Random Linear Codes
share
We propose a new heuristic algorithm for solving random subset sum instances a_1, ..., a_n, t ∈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.
READ FULL TEXT