Cryptology ePrint Archive: Report 2019/804

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

Claire Delaplace and Andre Esser and 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}}$.

Category / Keywords: public-key cryptography / time-memory trade-off, representations, parallel collision search

Date: received 11 Jul 2019

Contact author: andre esser at rub de

Available format(s): PDF | BibTeX Citation

Version: 20190714:155210 (All versions of this report)

Short URL: ia.cr/2019/804


[ Cryptology ePrint archive ]