Algorithms for public-key cryptography

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):

• Probabilities (L3)
• Computer Algebra (M1)
• Cryptography (M1)

Articles for the exam:

Evaluation