Table of Contents
Algorithmes arithmétiques pour la cryptologie / Arithmetic algorithms for cryptography (24h, 3 ECTS)Responsable : F. Morain. Équipe pédagogique
Planning, année/year 2020-2021Taught in Period 2: see below Thursday evenings from 16h15 to 19h15 (was supposed to be in Bâtiment Sophie Germain (P7), salle 1013), will take place via big blue button (or zoom in case this does not work). We are going to use a mathematical system for trying algorithms. If you don't a favorite one, try to install SAGE or Pari-GP. Also, we started a slack channel for the course, for which you should have received an invitation. More details will be available soon.
Course ObjectivesThis 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. PlanThe 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. PrerequisitesSpecific requirementsWe 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 backgroundThese 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. LanguageF. 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
Course notesSee the reference list. Assessment / ExaminationsThere will be one midterm and one final exam, both on paper. Documents and course notes are authorised; calculators and electronic devices are not. Past exams |