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

Claire Delaplace; Andre Esser; Alexander May

Paper 2019/804

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

Claire Delaplace, 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}, \dots, a_{n}, t)$ defined modulo $2^{n}$ , our algorithms improve over the Dissection technique for small memory $M < 2^{0.02 n}$ and in the mid-memory regime $2^{0.13 n} < M < 2^{0.2 n}$ . An application of our technique to LPN of dimension and constant error yields significant time complexity improvements over the Dissection-BKW algorithm from Crypto 2018 for all memory parameters .

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: time-memory trade-off representations parallel collision search
Contact author(s): andre esser @ rub de
History: 2019-07-14: received
Short URL: https://ia.cr/2019/804
License: CC BY

BibTeX

@misc{cryptoeprint:2019/804,
      author = {Claire Delaplace and Andre Esser and Alexander May},
      title = {Improved Low-Memory Subset Sum and {LPN} Algorithms via Multiple Collisions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/804},
      year = {2019},
      url = {https://eprint.iacr.org/2019/804}
}