INRIA SALSA
Université Paris 7 École Normale Supérieure de Cachan École Normale Supérieure École Polytechnique
UMPC Université Paris 11 École Nationale Supérieure des Télécommunications
Centre National de la Recherche Scientifique Commissariat à l'Energie Atomique Institut National de Recherche en Informatique et en Automatique
Home
Publications
Software
Teaching

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

Responsable : Jean-Charles Faugère

Intervenants 2014-2015

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 2014/2015


Bibliographie

 

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.

Les années précédentes

Équipe pédagogique

J.C. Faugère DR INRIA Paris-Rocquencourt
L Perret MC UPMC Lip6