2019/07/09 by Andre Esser, Esser, Andre, Alexander May +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CR #cs.DS
paper · pdf · doi:10.48550/arxiv.1907.04295
Issue with counting duplicate representations
openalex publication_date 2019/07/09 · openalex created_date 2019/07/23 · arxiv created 2019/10/21 · arxiv updated 2019/10/22 · openalex updated_date 2026/07/28
We propose a new heuristic algorithm for solving random subset sum instances a1, …, an, t ∈ ℤ2n, 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 20.291n for random subset sum, we improve (heuristically) down to 20.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 20.048n in the half distance decoding setting down to 20.042n.