Algorithms for public-key cryptography

CR10, CS M2, 2023-2024

Lecturers: Guillaume Hanrot, Benjamin Wesolowski

The purpose of this class is to introduce students to algorithmic aspects of public-key cryptography, a topic with a strong number-theoretic flavour (both algorithmic, algebraic and geometric). The class will be mainly focused on cryptanalysis, but will also address efficient algorithms for implementing public-key cryptographic primitives. We shall both study the pre-quantum world (for primitives & cryptanalysis) & the post-quantum world. The following topics will be studied.

I. Efficient arithmetic.

II. Discrete logarithm

III. Elliptic curves

IV. Interlude -- basics in algebraic number theory

V. Back to elliptic curves.

Prerequisites (advisable but not mandatory):

Articles for the exam:

  • S. Goldwasser, J. Kilian, Almost All Primes Can be Quickly Certified, STOC 1986, 316--329.
  • R. Baillie, A. Fiori, S. Wagstaff, Jr., Strengthening the Baillie-PSW Primality Test, Math. Comp. 90 (2021), 1931--1955.
  • I. Duursma, P. Gaudry, F. Morain Speeding up the Discrete Log Computation on Curves with Automorphisms, Asiacrypt'99, 103--121.
  • R. P. Brent, P. Gaudry, E. Thomé, P. Zimmermann, Faster Multiplication in GF(2)[x], ANTS 2009, 153-166.
  • R. Granger, T. Kleinjung, A.K. Lenstra, B. Wesolowski, J. Zumbrägel,Computation of a 30 750-Bit Binary Field Discrete Logarithm, Math. Comp. 90 (2021), 2997-3022.
  • C. Bouvier, G. Castagnos, L. Imbert, F. Laguillaumie, I want to ride my BICYCL: BICYCL Implements CryptographY in CLass groups, J. Cryptol. 36 (2023), article 17.
  • W. Castryck, J. Sotakova, F. Vercauteren,Breaking the decisional Diffie-Hellman problem for class group actions using genus theory -- extended version, J. Cryptol. 35 (2022), article 24.
  • A. Basso et al. Supersingular Curves You Can Trust, Eurocrypt'2023, 405--437.
  • M. Corte-Real Santos, C. Costello, J. Shi Accelerating the Delfs--Galbraith algorithm with fast subfield root detection, Crypto'2022, 285--314.
  • J. Bos, C. Costello, A. Miele, Elliptic and Hyperelliptic Curves: A Practical Security Analysis, PKC'2014, 203--220.
  • T. B. Fouotsa, T. Moriya, C. Petit M-SIDH and MD-SIDH: countering SIDH attacks by masking information, Eurocrypt'2023, 282--309.
  • Evaluation

    Homework (50%) and final exam (oral, 50%).