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

Abstract

For enabling post-quantum cryptanalytic experiments on ameaningful scale, there is a strong need for low-memory algorithms. Weshow that the combination of techniques from representations, multiplecollision finding, and the Schroeppel-Shamir algorithm leads to improvedlow-memory algorithms.For random subset sum instances (a1,...,an,t) defined modulo 2n,our algorithms improve over the Dissection technique for small memoryM<20.02nand in the mid-memory regime 20.13n<M <20.2n.An application of our technique to LPN of dimensionkand con-stant errorpyields significant time complexity improvements over theDissection-BKW algorithm from Crypto 2018 for all memory parameters M<20.35 klogk.