Résumé

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 leads to improved low-memory algorithms. For random subset sum instances (a₁, ..., a_n, t) defined modulo 2ⁿ, 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.35k/log k.}

This is joint work with Andre Esser and Alexander May.