Le prochain séminaire SSL sera donné par Emmanuel Thomé, de l’équipe CARAMBA le jeudi 12 mars, à 13h30, en salle A008.

Titre : Large-scale computational records for public-key cryptography

Résumé :
Joint work with Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Paul Zimmermann.

In December 2019 and February 2020, we completed several record computations related to hard problems in public-key cryptography: we factored a 240-digit RSA modulus, we computed discrete logarithms modulo a 240-digit prime, and while we were at it, we also factored a 250-digit RSA modulus. Such records provide very important data points for the assessment of the computational hardness of the integer factorization (IF) and finite field discrete logarithm (DL) problems. These problems underpin the largest part of public-key cryptography that is currently in use. Previous records date back to 2016 (for DL) and 2009 (for IF).

This talk reports on how these computations were performed, and on how we chose parameters for the Number Field Sieve algorithm in order to minimize the running time. We also give some data on the scalability of our approach, and how it required harnessing a formidable computing power, with thousands of CPU cores from several facilities, working in parallel over several months. We also show that our work goes well beyond improving on previous records by using a lot of hardware: even if we had used identical hardware, our larger computation would have been faster than the smaller, previous record (for DL).