Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Mars 2020

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

par Claire Delaplace (Univ. Bochum, Allemagne)

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 (a1, ..., an, t) defined modulo 2n, our algorithms improve over the Dissection technique for small memory M < 20.02n and in the mid-memory regime 20.13n < M < 20.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 < 20.35k/log k.

This is joint work with Andre Esser and Alexander May.

GREYC
Université de Caen Normandie
Campus Côte de Nacre
Boulevard du Maréchal Juin
Bâtiment Sciences 3
CS 14032
14032 CAEN cedex 5
TEL : +33 (0)2 31 56 74 86
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr