Systèmes polynomiaux, calcul formel et applications (24h, 3 ECTS)

Responsable : Jean-Charles Faugère

Intervenants 2022-2023

• Jean-Charles Faugère: Systèmes d'équations algébriques, bases de Groebner, Applications en Cryptographie.
• Mohab Safey El Din: Applications. Systenes Polynomiaux.

Objectifs

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).

Plan du cours

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.

 

Planning 2022/2023

Bibliographie

• 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.

  Prérequis

  De bonnes connaissances de base en algèbre élémentaire (linéaire, multi-linéaire) ainsi que les structures fondamentales que sont les groupes anneaux et corps sont fortement souhaitables. Des connaissances solides en analyse de base (niveau L1 ou L2) sont aussi recommandées (notions de continuité, dérivées, théorème des fonctions implicites).

  Il est aussi recommandé d’avoir quelques notions d’algorithmique élémentaire et de complexité (notation “grand O”) ainsi qu’une connaissance des structures de données élémentaires que sont les tableaux, listes, et arbres.

  Cours liés

  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 à la cryptologie, nous ne ferons pas les bases de la cryptologie, juste l'introduction des problèmes que nours traiterons.

  2.12-2 Algorithmes arithmétiques pour la cryptologie. Bien que nous discuterons d'applications à la cryptologie, nous ne ferons pas les bases de la cryptologie, juste l'introduction des problèmes que nours traiterons.

  2.14-1 Analyse Géométrique des Données. Pour des applications potentielles du Calcul Formel.

  Stages/internships

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

• Internship Master M2: Efficient algorithms for computing structured polynomial systems and applications.

 

English Policy

We accept to do the lectures in English if there is at least one non French speaking student in the audience, and no French speaking student is opposed to lectures in English.

 

Slides in English will be available.

Équipe pédagogique

J.C. Faugère	DR	INRIA	CryptoNext & INRIA Paris
M Safey El Din	PR	SU