6
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Better Sample -- Random Subset Sum in \(2^{0.255n}\) and its Impact on Decoding Random Linear Codes

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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}\).

          Related collections

          Most cited references20

          • Record: found
          • Abstract: not found
          • Article: not found

          Hiding information and signatures in trapdoor knapsacks

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Computing Partitions with Applications to the Knapsack Problem

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              A Generalized Birthday Problem

                Bookmark

                Author and article information

                Journal
                09 July 2019
                Article
                1907.04295
                e0eb5bed-2b6f-4a58-9077-8ce96b96c8e2

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.DS cs.CR

                Data structures & Algorithms,Security & Cryptology
                Data structures & Algorithms, Security & Cryptology

                Comments

                Comment on this article