ALMASTY
Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions
18/11/2021Intervenant(s) : Claire Delaplace
For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We present low memory algorithms for subset-sum and LPN based on a combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm. For random subset sum instances 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 techniques 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 k/log k}$. This is a joint work with Andre Esser and Alexander May published at IMACC 2019.
damien.vergnaud (at) nulllip6.fr