- title:
- Arithmetic Algorithms for Cryptography
Algorithmes arithmétiques pour la cryptologie - manager:
- Ben Smith
- ects:
- 3
- period:
- 1
- hours:
- 24
- weeks:
- 8
- hours-per-week:
- 3
- language:
- English
- lang:
- track:
- C
- themes:
- Cryptography
- order:
- 2.12.2
- successor:
- cryptalg
- link:
- view
- [2.12.2]
- Arithmetic Algorithms for Cryptography
Algorithmes arithmétiques pour la cryptologie
- Language:
- Period:
- 1.
- Duration:
- 24h (3h/week).
- ECTS:
- 3.
- Themes: Cryptography
- Manager:
- Ben Smith.
Équipe pédagogique
| Benjamin Smith | CR | INRIA | LIX |
Planning, année/year 2024-2025
Friday mornings from 8h45 to 11h45 (in Period 1) in Bâtiment Sophie Germain (P7), salle 1002.
Slides and other resources will be posted online at https://www.lix.polytechnique.fr/~smith/MPRI/ (contact B. Smith for access).
| Date | Class | Teacher | Details |
|---|---|---|---|
| 20/09/24 | Lecture 1 | Smith | Primes, generic groups, discrete logarithms, and Shoup's theorem |
| 27/09/24 | — | No class | |
| 04/10/24 | Lecture 2 | Smith | From the multiplicative group to elliptic curves |
| 11/10/24 | Lecture 3 | Smith | Elliptic curve factoring and modern elliptic curve cryptosystems |
| 18/10/23 | Lecture 4 | Smith | Isogenies and endomorphisms |
| 25/10/24 | Lecture 5 | Smith | Point counting algorithms and the construction of secure curves |
| 01/11/24 | — | No class | Toussaint holiday |
| 08/11/24 | Lecture 6 | Smith | Pairings and pairing-based cryptography |
| 15/11/24 | Lecture 7 | Smith | Isogenies and post-quantum group-action-based cryptography I |
| 22/11/24 | Lecture 8 | Smith | Isogenies and post-quantum group-action-based cryptography II |
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 (especially elliptic curves). We consider not only contemporary discrete-logarithm-based cryptosystems, but also newer isogeny-based cryptosystems designed to resist quantum attacks. We also describe the advanced number-theoretic algorithms required to derive secure parameters. 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 part of a solid introduction to contemporary cryptography when taken together with the other MPRI cryptography courses, including 2-12-1, 2-13-1, 2-13-2, and 2-30.
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
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 final exam, on paper. Documents and course notes are authorised; calculators and electronic devices are not.