Welcome to the resource topic for
**2019/804**

**Title:**

Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

**Authors:**
Claire Delaplace, Andre Esser, Alexander May

**Abstract:**

For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We show that the combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm leeds to improved low-memory algorithms. For random subset sum instances (a_1, \ldots, a_n,t) defined modulo 2^n, our algorithms improve over the Dissection technique for small memory M < 2^{0.02n} and in the mid-memory regime 2^{0.13n} < M < 2^{0.2n}. An application of our technique to LPN of dimension k and constant error p yields significant time complexity improvements over the Dissection-BKW algorithm from Crypto 2018 for all memory parameters M< 2^{0.35 \frac{k}{\log k}}.

**ePrint:**
https://eprint.iacr.org/2019/804

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 .