Algorithms for public-key cryptography
CR10, CS M2, 2023-2024
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
- Quadratic number fields, quadratic integers.
- 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.
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%).