CRYPTO : Claire Delaplace (Ruhr Uni Bochum) : Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé

CRYPTO : Claire Delaplace (Ruhr Uni Bochum) : Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

25 mars 2019 / 11:00 - 12:00

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_1, …, 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 k / log k). Joint work with Andre Esser and Alexander May.

CRYPTO : Claire Delaplace (Ruhr Uni Bochum) : Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

Détails

Date :
25 mars 2019
Heure :
11:00 - 12:00
Catégorie d’évènement:

Lieu

Bâtiment Descartes, salle 301

Organisateur

Luca de Feo