Responsable : Jean-Charles Faugère

• Jean-Charles Faugère: Polynomial systems, Gröbner bases, Applications in Cryptography.
• Mohab Safey El Din: Polynomial systems, Gröbner bases, Applications in geometry and engineering sciences.

Courses are taught in English upon request else, by default, they are taught. All lecture notes, slides and exercises are written in English.

Good knowledge on elementary algebra structures (groups, rings, fields) and paradigms (linear, multi-linear) are required. Basic notions of mathematical analysis (continuity, derivatives, taylor developments and related notions on series, implicit function theorem) are expected.
Basic notions in elementary algorithmics and complexity (big Oh notation) as well as elementary data-structures (arrays, lists, trees) are expected.

Cette annee le cours 2-13-1 est centré sur la résolution des systèmes polynomiaux par le calcul de bases de Gröbner et leurs applications en cryptologie (c'est a dire que les solutions et les coefficients des polynomes sont dans un corps fini).

Les systèmes polynomiaux interviennent dans de nombreux de domaines des sciences de l’ingénieur ou de l’informatique, notamment en cryptologie, robotique, théorie du signal, et géométrie algorithmique. Le calcul formel est la manipulation par l’ordinateur des expressions mathématiques. Les algorithmes algébriques du Calcul Formel constituent un outil privilégié pour la résolution exacte et certifiée des systèmes polynomiaux (la non-linéarité de ces derniers rendant délicates les approches purement numériques). Le but de ce cours est de donner les algorithmes efficaces de résolution de ces systèmes ainsi que de décrire une applications phare de ces méthodes en cryptologie. Le cours s’articule autour de deux axes. Le premier traite du calcul de base de Gröbner et constitue le coeur de la résolution algébrique utilisé dans la suite. Dans cette partie du cours nous decrivons les algorithmes les plus efficaces pour le Calcul des bases Grobner (algorithmes F4 et F5) et nous donnons des resultats de complexite de Groebner qui seront utilises pour les applications en cryptologie. Le second axe étudie comment la résolution des systèmes polynomiaux (dans les corps finis) permet d’évaluer et/ou concevoir certains cryptosystèmes , la modélisation et la structure des systèmes polynomiaux jouent ici un rôle crucial.

Plusieurs applications en cryptologie utilisant les méthodes algébriques illustrent le cours: construction et cryptanalyse de nouveaux cryptosystèmes (Mc Eliece, famille HFE, ...) et cryptanalyse de cryptosystèmes existants (chiffrement par flot, chiffrement par blocs, HFE, ...). Un nouvel exemple d'application sera presente cette annee: il s'agit du probleme du logarithme discret sur les courbes algebriques (EC DLP).

Systèmes polynomiaux, calcul formel et applications

 

Le cours s’articule autour des deux axes suivants :

• Calcul de bases de Gröbner pour la résolution des systèmes polynomiaux : cet axe constitue le noyau d’algorithmique algébrique sur lequel repose l’ensemble des algorithmes donnés dans la suite ; les algorithmes les plus récemment introduits seront étudiés ; ceux-ci reposent sur une réduction à des problèmes d’algèbre linéaire ; ils permettent en outre d’effectuer efficacement des opérations de base sur les idéaux polynômiaux (élimination de variables, saturation, intersection).
• Application en Cryptologie : cet axe étudie comment les calculs de bases de Gröbner peuvent être utilisés pour le design de nouveaux cryptosystèmes et/ou l’analyse de la sécurité de cryptosystèmes existants (Cryptanalyse algébrique) ; les systèmes polynômiaux considérés ici sont à coefficients dans un corps fini et sont parfois très structurés. L’accent est mis sur la modélisation des problèmes.

Tuesday, from 16h00 to 19h00, Building Sophie Germain, room 1004

• Course 1: Introduction to polynomial system solving, Ideals and Varieties, Nullstellensatz.
• Course 2: Zariski topology, dimension and degree. Properties of polynomial ideals. Definition of Gröbner bases
• Course 3: Multivariate division and ideal membership problem, Dickson's lemma and Buchberger's criterion
• Course 3: Buchberger's algorithm and optimizations, Additional properties of Gröbner bases
• Course 4: Hilbert series, regualar sequences and degree of regularity
• Course 5: Lazard's algorithm, complexity under genericity assumptions
• Course 6: F4 algorithm: basic properties, optimizations and complexity results
• Course 7: F5 algorithm: basic properties, optimizations and complexity

• Introduction et rappels:

  Jean-Charles Faugère et Mohab Safey El Din Chapitre d’introduction à la résolution des systèmes polynomiaux (avec exercices) . Ouvrage collectif chez Pearson Education.

• Pour les aspects systèmes algébriques
• D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, 1996. second edition.
• T. Becker and V. Weispfenning. Gröbner bases. Springer-Verlag, New York-Berlin-Heidelberg, 1993.

2.22 Algorithmes efficaces en calcul formel Pour ceux qui veulent voir d'autres aspects du calcul formel.

2.12-1 Techniques en cryptographie et cryptanalyse

          Bien que nous discuterons d'applications a la cryptologie, nous ne
          ferons pas les bases de la cryptologie, juste l'introduction des
          problèmes que nours traiterons. 
          

2.12-2 Algorithmes arithmetiques pour la cryptologie.

          Bien que nous discuterons d'applications à la cryptologie, nous ne
          ferons pas les bases de la cryptologie, juste l'introduction des
          problemes que nours traiterons. 
          

Des stages seront proposé par l'équipe-projet POLSYS de l'INRIA Rocquencourt tout au long de l'annee 2013/2014.