# 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.

• Algorithms for multiple precision arithmetic & polynomials: representation, addition, multiplication, division
• Gcd, arithmetic mod N / mod P(x). Montgomery arithmetic. Fast exponentiation and variants.
• Basics of primality : probabilistic testing for integers (under GRH) ; irreducibility test for polynomials over finite fields. Complexity of constructing a random prime / irreducible poly in F_p.
• Z/NZ & finite fields. Mathematical structure. Finding a generator.

#### II. Discrete logarithm

• Mathematical definition. Simple crypto applications.
• Discrete logarithms : Pollard rho, Pohlig-Hellman, lower bound in the generic group model. Index calculus in finite fields (large & small characteristic)
• Quantum algorithms: Shor's algorithm.
• Algorithms for (Z/pZ)^* : Adleman ; Z[i]-algorithm ; sieving ; towards NFS.
• Algorithms for (F_q)^* : Adleman ; quasipolynomial.

#### III. Elliptic curves

• Definition, group law.
• Isogenies
• Isogeny graph, random walks, link with collision search / DL

#### IV. Interlude -- basics in algebraic number theory

• Ideals, factorisation of ideals, factorisation of primes.
• Class group, class number; explicit algorithms for class group.

#### V. Back to elliptic curves.

• Class group action.
• CSIDH.

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%).