Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Algorithmes arithmétiques pour la cryptologie / Arithmetic algorithms for cryptography (24h, 3 ECTS)

Responsable : F. Morain.

Équipe pédagogique

François MorainPUÉcole polytechniqueLIX
Benjamin SmithCRINRIALIX

Planning, année/year 2019-2020

Taught in Period 1 and Period 2: see below

Tuesday evenings from 16h15 to 17h55 in Bâtiment Sophie Germain (P7), salle 1013.

17/09 François Morain Generic groups; Z/NZ and applications
24/09 François Morain Elementary integer factorization
01/10 François Morain Continued fractions and applications; quantum integer factorization
08/10 François Morain L[1/2] factoring and discrete logarithms computations
15/10 François Morain Number field sieve
22/10 François Morain Computing discrete logarithms in small characteristic
29/10 François Morain TD/Lab
05/11 Ben Smith ECM and basic ECC protocols
12/11 Ben Smith Real-world ECM and ECDH: Montgomery arithmetic
19/11 (no class)
26/11 Midterm exam
03/12 (no class)
10/12 Ben Smith
17/12 Ben Smith
Holidays
07/01 Ben Smith
14/01 Ben Smith
21/01 Ben Smith
28/01 Ben Smith
04/02 Ben Smith
11/02 Ben Smith
18/02 (no class)
25/02 (no class)
03/03 Final exam

Course Objectives

This course aims to present the concepts and tools of modern number-theoretic public-key cryptography, whose mathematical building blocks are finite fields and algebraic curves (elliptic and hyperelliptic). We consider not only contemporary discrete-logarithm-based cryptosystems, but also newer isogeny-based cryptosystems designed to resist quantum attacks. This course also forms an introduction to algorithmic number theory, an alliance of classical number theory with algorithms and complexity theory, with applications in cryptography.

This course forms a solid introduction to contemporary crypto when taken together with the other MPRI cryptography courses, including 2-12-1, 2-13-1, 2-13-2, and 2-30.

Plan

The course is split into two parts:

Cryptographic groups, factorization, and discrete logarithms: 9 hours (François Morain)
Modern and postmodern elliptic curve cryptography – 15 hours (Ben Smith)

The second part of the course is an introduction to contemporary elliptic-curve cryptography (ECC), including hyperelliptic cryptosystems and pairings. It also describes a new generation of isogeny-based cryptosystems, which are designed to resist attacks by quantum algorithms. After describing the basic properties and arithmetic of elliptic curves, we consider the current state-of-the-art in elliptic-curve cryptographic primitives. This requires a study of basic algorithms including efficient arithmetic, point-counting, and the hardness of the discrete logarithm problem, as well as deeper problems like the computation of isogenies and the navigation of isogeny graphs. We also give an introduction to cryptographic pairings, used in many more advanced cryptosystems.

Prerequisites

Specific requirements

We assume that students have already followed an introductory course in cryptography, and are familiar with modular arithmetic and finite fields. No prior knowledge of algebraic curves is assumed.

General background

These prerequisites are not specific to cryptography, and are already essentially included in the list of general prerequisites for MPRI.

Students must be familiar with complexity classes, Turing machines, and NP problems. Basic notions in algebra and probability are also required, together with a mastery of common foundational algorithms.

Language

F. Morain donne sa partie du cours en français ou en anglais suivant la demande (english on request).

B. Smith will teach in English.

All course materials (documentation and slides) will be given in English.

Useful references

  • A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press.
  • J. von zur Gathen, J. Gehrard, Modern Computer Algebra, Cambridge University press, 1999, seconde édition 2003.
  • V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005, 2nd ed. 2008.
  • R. P. Brent, P. Zimmermann, Modern Computer Arithmetic, manuscrit en préparation, disponible en ligne.
  • G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Clarendon Press, 5th edition, 1985.
  • D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley, 2nd edition, 1981.
  • H. Cohen, A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer–Verlag, 1996.
  • P. Ribenboim, The new book of prime number records, Springer-Verlag, 1996.
  • R. Crandall and C. Pomerance, Primes – A Computational Perspective, Springer Verlag, 2000.
  • F. Morain, La primalité en temps polynomial (d'après Adleman, Huang; Agrawal, Kayal, Saxena), S\'eminaire Bourbaki, Mars 2003.
  • H. Riesel, Prime numbers and computational methods for factorization, Progress in Mathematics, 57. Birkhauser 1985.

Course notes

See the reference list.

Assessment / Examinations

There will be one midterm and one final exam, both on paper. Documents and course notes are authorised; calculators and electronic devices are not.

Past papers

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA