The school will host the following courses:
L'école sera constituée des cours suivants :
- Algorithmic Number Theory
by Cécile Armana (University of Franche-Comté, France)
Abstract - La cryptographie basée sur les courbes elliptiques
by Sorina Ionica (University of Picardie Jules Verne, France)
Abstract - Diophantine equations
by Florian Luca (University of the Witwatersrand, South Africa)
Abstract - La cryptographie basée sur les réseaux
by Abderrahmane Nitaj (University of Caen-Normandy, France)
Abstract - Elementary number theory and cryptography
by Alain Togbe (Purdue University Northwest, USA)
Abstract - Elementary approach to elliptic curves
by Michel Waldschmidt (University Paris 6, France)
Abstract Lecture notes - Some aspects of algebraic number theory related with cryptography
by Claude Levesque (Université Laval, Canada)
Abstract
Abstracts / Résumés
Algorithmic Number Theory (Cécile Armana, 6 hours)
Number theory has long been inseparable from algorithms. Finding efficient algorithms may help to understand the structure of numbers and to explore this structure, we are assisted by the algorithms we already have. In this course we will start with classical algorithms and their analysis (Horner method for evaluating polynomials, modular arithmetic, Euclidean algorithms, exponentiation by squaring,...). We will then focus on algorithms more specific to number theory (squares modulo a prime number, (pseudo)-primality tests, factorization of integers). If time allows, we will discuss advanced algorithms based on elliptic curves (Schoof's algorithm for counting points on elliptic curves over finite fields, Lenstra's factorization algorithm of integers, elliptic curve primality tests).
References:
-
Victor Shoup, A computational introduction to number theory and algebra. Cambridge University Press, second edition (2008). File available at https://shoup.net/ntb/ntb-v2.pdf
-
Steven Galbraith, Mathematics of Public Key Cryptography. Cambridge University Press (2012). Full extended text available at https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf
-
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Second Edition. Springer (2005).
-
David Bressoud, Factorization and Primality Testing. Undergraduate Texts in Mathematics, Springer (1989).
-
Henri Cohen, A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, Springer (1993).
La cryptographie basée sur les courbes elliptiques (Sorina Ionica, 6 hours)
Ce cours aborde les principaux thèmes mathématiques pour s'initier à la cryptographie basée sur les courbes elliptiques. Le cours est composé des chapitres suivants:
- Chapitre 1: Le protocole de Diffie-Hellman et le système d'ElGamal - mise en oeuvre à l'aide des courbes elliptiques
- Chapitre 2: Attaques élémentaires du problème du logarithme discret sur des courbes elliptiques
- Chapitre 3: Introduction à la cryptographie à base d'isogénies.
Références :
-
Steven Galbraith, Mathematics of public key cryptography, Cambridge University Press, 2012. Full extended text available at https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf
-
Antoine Joux, Algorithmic Cryptanalysis, Chapman and Hall/CRC (24 juin 2009).
-
Joseph Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, Springer Verlag, 2009.
-
Handbook of elliptic and hyperelliptic curve cryptography, Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, Frederik Vercauteren, Chapman and Hall/CRC, 2005.
Diophantine equations (Florian Luca, 6 hours)
Linear equations, quadratic equations (parametrization of Pythagorean triples, Pell equations), Applications of modular arithmetic to the resolution of exponential Diophantine equations. Applications of linear forms in logarithms.
References:
-
Y. Bugeaud, Linear forms in logarithms and applications, IRMA Lectures in Mathematics and Theoretical Physics, 28. European Mathematical Society (EMS), Zürich, 2018.
-
B. M. M. de Weger, B. M. M. Algorithms for Diophantine equations. CWI Tract, 65. Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1989. File available at https://www.win.tue.nl/~bdeweger/downloads/CWI%20Tract%2065.pdf
-
F. Luca, Exponential Diophantine equations, Notes from the International Autumn School on Computational Number Theory, 267–309, Tutor. Sch. Workshops Math. Sci., Birkhäuser/Springer, Cham, 2019. File available at https://link.springer.com/content/pdf/10.1007%2F978-3-030-12558-5_4.pdf
-
T. N. Shorey; R. Tijdeman, Exponential Diophantine equations. Cambridge Tracts in Mathematics, 87. Cambridge University Press, Cambridge, 1986.
La cryptographie basée sur les réseaux (Abderrahmane Nitaj, 8 hours)
Ce cours aborde les principaux thèmes mathématiques pour s'initier à la cryptographie basée sur les réseaux. Le cours est composé des chapitres suivants :
- Chapitre 1: Introduction aux réseaux et aux problèmes difficiles.
- Chapitre 2 : Les système NTRU et LWE.
- Chapitre 3: Application des réseaux à la cryptanalyse de RSA et de NTRU.
Chaque chapitre sera mis en pratique à l'aide du système de calcul Python.
Références :
-
Nguyen, Phong Q., Vallée, Brigitte: The LLL Algorithm, Survey and Applications, Information Security and Cryptography, Springer-Verlag Berlin Heidelberg 2010.
-
Tancrède Lepoint: Design and Implementation of Lattice-Based Cryptography, Cryptography and Security, École Normale Supérieure de Paris - ENS Paris, 2014. Available at https://tel.archives-ouvertes.fr/tel-01069864/document
-
Chris Peikert: A Decade of Lattice Cryptography, February 17, 2016. Available at https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf
-
Federico Bergami: Lattice-Based Cryptography, ALGANT Master’s Thesis - 20 July 2016. Available at https://www.math.u-bordeaux.fr/~ybilu/algant/documents/theses/BERGAMI.pdf
Elementary number theory and cryptography (Alain Togbé, 7 hours)
In this course, we will introduce the basics of the elementary number theory to introduce cryptography. So we will use the theory of congruences to gently introduce cryptography. We will start from the Caesar cipher to present the public-key cryptography. We will also discuss the knapsack cryptosystem (which is based on the difficult classic problem in combinatorics known as the knapsack problem) and the discrete logarithm problem.
References:
- David M. Burton, Elementary Number Theory, seventh edition, McGraw-Hill.
- J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography, Springer.
Elementary Approach to Elliptic Curves (Michel Waldschmidt, 6 hours)
Examples of elliptic curves, drawing elliptic curves, the set of rational points of an elliptic curve, intersection of a line and an elliptic curve, the point at infinity of an elliptic curve, basics of projective geometry, singular points, the group law, Weierstrass equations and their classification, elliptic curves over finite fields and their properties, the Hasse bound, the structure of the group of points over finite fields, applications to cryptography.
Lecture notes
References:
- J. H. Silverman, The Arithmetic of Elliptic Curves, Chapters III, V and VIII. (Graduate Texts in Mathematics) 2nd ed. 2009 Edition, Springer.
- K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, (Graduate Texts in Mathematics) 2nd ed. 1998, Springer.
Some aspects of algebraic number theory related with cryptography (Claude Levesque, 6 hours)
This course will focus on binary quadratic forms. There are useful to compute the class number of real quadratic fields. There is a cryptosystem based on the class group of quadratic fields that resists attacks made with quantum computers.
