Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Codes correcteurs d'erreurs, calcul formel: applications à la cryptologie (48h, 6 ECTS)

Responsables : Jean-Charles Faugère et Jean-Pierre Tillich

Intervenants 2008-2009

<dd>

  • Jean-Charles Faugère: systèmes d'équations algébriques, leur résolution efficace.
  • Ludovic Perret: Applications en Cryptographie.
  • Daniel Augot: théorie algébrique des codes.
  • Nicolas Sendrier Cryptographie basée sur les codes.
  • Jean-Pierre Tillich: théorie de l'information et méthodes probabilistes en codage.

</dd>

Objectifs

Le but du cours est de présenter les techniques de protection de l'information numérique fondé sur la théorie algébrique des codes correcteurs d'erreurs et les outils de Calcul Formel permettant de résoudre ou manipuler les équations algébriques dans les corps finis. On montre aussi dans le cours comment ces techniques algébriques et de codage fournissent des outils puissants et généraux de cryptanalyse.

La _théorie algébrique des codess'est développée à partir des problèmes posés par la résistance au bruit ; les codes correcteurs doivent protéger une information transitant à travers un canal de transmission soumis à des perturbations. Ce canal peut être une ligne téléphonique, une liaison radio ou encore un support magnétique ou optique. Le codage consiste en l'ajout d'une redondance, et le décodage doit permettre, à partir de la sortie codée puis perturbée du canal, de restituer de façon acceptable l'information fournie par la source. Après une introduction générale aux codes correcteurs, le cours portera sur les algorithmes de décodage. Tous les principaux aspects du décodage sont abordés (décodage par liste, décodage itératif, algorithme de Sudan). Les algorithmes de codage/décodage utilisent fortement les structures algébriques: corps finis, algèbre linéaires dans les corps finis, polynômes à une ou plusieurs variables, factorisation des polynômes, résolution d'équations algébriques, .... Le Calcul Formel dont le but est la manipulation par ordinateur d'expressions mathématiques fournit des algorithmes efficaces pour traiter ces problèmes. En particulier les algorithmes récents pour le calcul des bases de Gröbner sont présenté dans le cours; ces algorithmes permettent de traiter efficacement, en particulier dans les corps finis, le problème de la résolution des systèmes d'équations algébriques (plusieurs équations en plusieurs variables). Plusieurs applications en cryptologie utilisant les codes ou les méthodes algébriques illustrent le cours: construction de nouveaux cryptosystèmes (Mc Eliece, famille HFE, ...) et cryptanalyse de cryptosystèmes existants (chiffrement par flot, chiffrement par blocs, HFE, ...). Le cours évolue cette année vers une interaction plus forte entre la partie plus théorique (codes et Calcul Formel) et les applications à la Cryptologie ==== Plan du cours ==== <html><dl> <dt>Codes correcteurs d'erreurs</dt> <dd> * Théorie générale des codes (Shannon). * Codes cycliques et géométriques. * Mise en équations algébriques du problème de décodage/distance min. * Cryptosystème fondé sur les codes: MacEliece, fonctions de hachage. * Algorithme de Sudan. Application en cryptanalyse. * Décodage itératif. * Aplications des techniques de décodage à la cryptanalyse. </dd> <dt>Calcul Formel</dt> <dd> * Idéaux et variétés. Resolution des systèmes algébriques. * Algorithme pour le calcul des bases de Gröbner (Buchberger, F4, F5). * Suite régulière et semi-régulière. * Complexité des bases de Grobner. Systemes sur determines. * Cryptanalyse algébrique avec les bases de Gröbner (Immunite algebrique, ...) * Cryptographie multivariee </dd> </dl></html> ==== <a name=“Planning20082009”> ]] Planning 2008/2009 ==== <TABLE height=“801” border=3D1 cellPadding=3D1 cellSpacing=3D0> <TBODY> <TR> <TD noWrap align=3Dmiddle>Date</TD> <TD noWrap align=3Dmiddle>Titre du Cours</TD> <TD noWrap align=3Dmiddle>Enseignant</TD> <TD noWrap align=3Dmiddle>Support de cours </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>18/09/2008</TD> <TD noWrap align=3Dmiddle>Introduction générale</TD> <TD noWrap align=3Dmiddle>L. Perret </span>, Jean-Pierre Tillich</TD> <TD noWrap align=3Dmiddle>Introduction GB et Crypto </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>25/09/2008</TD> <TD noWrap align=3Dmiddle>Introduction à la cryptographie multivariée. Introduction aux bases de Grobner </TD> <TD noWrap align=3Dmiddle>L. Perret</TD> <TD noWrap align=3Dmiddle>Cryptographie multivari&eacute;e Introduction aux GB </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>02/10/2008</TD> <TD noWrap align=3Dmiddle>Principe de la cryptanalyse algébrique. Cryptanalyse de HFE et IP. </TD> <TD noWrap align=3Dmiddle>L. Perret</TD> <TD noWrap align=3Dmiddle>Cryptanalyse alg&eacute;brique </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>09/10/2008</TD> <TD noWrap align=3Dmiddle>Bases de Gröbner Idéal, Variétés. </TD> <TD noWrap align=3Dmiddle><span class=“Style18”>L. Perret </span></TD> <TD noWrap align=3Dmiddle>Cryptanalyse avanc&eacute;e </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>16/10/2008</TD> <TD noWrap align=3Dmiddle>Ideaux - Varietes Bases de Groebner - Algorithme de Buchberger </TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JC Faug&egrave;re</span></TD> <TD noWrap align=3Dmiddle>Algorithme de Buchberger </TD> </TR> <P> <TR> <TD noWrap align=3Dmiddle>23/10/2008</TD> <TD noWrap align=3Dmiddle>Annulation</TD> <TD noWrap align=3Dmiddle> </TD> <TD noWrap align=3Dmiddle> </TD> </TR> <TR> <TD noWrap align=3Dmiddle>30/10/2008</TD> <TD noWrap align=3Dmiddle>Optimisations de l'algorithme de Buchberger FGLM - escalier - frontiere</TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JC Faug&egrave;re</span></TD> <TD noWrap align=3Dmiddle>Criteres de Buchberger</TD> </TR> <TR> <TD noWrap align=3Dmiddle>6/11/2008</TD> <TD noWrap align=3Dmiddle>FGLM Algorithme F4</TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JC Faug&egrave;re</span></TD> <TD noWrap align=3Dmiddle>Algorithme F4</TD> </TR> <TR> <TD noWrap align=3Dmiddle>13/11/2008</TD> <TD noWrap align=3Dmiddle> devoir a la maison + questions. Algorithme F5 + Complexite</TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JC Faug&egrave;re</span></TD> <TD noWrap align=3Dmiddle> Algorithme F5</TD> </TR> <TR> <TD noWrap align=3Dmiddle>20/11/2008</TD> <TD noWrap align=3Dmiddle>Pas de cours (semaine examen)</TD> <TD noWrap align=3Dmiddle> </TD> <TD noWrap align=3Dmiddle> </TD> </TR> <TR> <TD noWrap align=3Dmiddle>27/11/2008</TD> <TD noWrap align=3Dmiddle>Théorème de Shannon </TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JP Tillich</span></TD> <TD noWrap align=3Dmiddle><span class=“Style18”></span></TD> </TR> <TR> <TD noWrap align=3Dmiddle>4/12/2008</TD> <TD noWrap align=3Dmiddle>Théorème de Shannon (suite et fin) bornes sur la distance minimale d'un code </TD> <TD noWrap align=3Dmiddle><span class=“Style18”>JP Tillich</span></TD> <TD noWrap align=3Dmiddle><span class=“Style18”></span></TD> </TR> <P> <td height=“9”></P></TBODY></TABLE> <BR> ==== Bibliographie ==== <ul> <li> Pour les aspects systèmes algébriques</li> * 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. <li> Pour le codage et la théorie de l'information</li> * Steven Roman. Coding and Information Theory. Graduate Texts in Mathematics, Springer, 1992. * Ron Roth. Introduction to Coding Theory. Cambridge University Press, 2006. * Madhu Sudan. Essential Coding THeory. Notes de cours disponibles sur en ligne. </ul> ==== Prérequis ==== Algèbre commutative. Nous utiliserons beaucoup les corps finis (finite fields), sans faire de rappels sur leur construction et leurs propriétés. ==== Cours liés ==== 2.12 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.22 Algorithmes efficaces en calcul formel. Pour ceux qui veulent voir d'autres aspects du calcul formel. ==== Stages/internships ==== (mise a jour le21 novembre 2008)<P> Il reste encore quelques stages proposé par l'équipe-projet SALSA de l'INRIA Rocquencourt (contact dans le sujet du stage): <ul> <li> Optimisation algebrique sous contraintes et calcul formel. <li> Solutions reelles des systemes polynomiaux : calcul d'invariants geometriques. </ul> Stages proposés par l'UCL (Louvain en Belgique) <ul> <li>quatre sujets </ul> Stages proposés dans l'entreprise Oberthur Card Systems <ul> <li>Fonctions de Hachage</li> <li>Protection against Fault Attacks</li> </ul> ==== 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. ==== Les années précédentes ==== * Année 2009-2010 * Année 2008-2009 * Année 2007-2008 * Année 2006-2007 ==== Équipe pédagogique ==== |J.C. Faugère|DR|INRIA|Paris-Rocquencourt| |L. Perret|MC|UPMC|Lip6| |D. Augot|CR|INRIA|Rocquencourt| |N. Sendrier|DR|INRIA|Rocquencourt| |J.P. Tillich|CR|INRIA|Rocquencourt| —— * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.JeanPierreTillich, %MAINWEB%.JeanCharlesFaugere, %MAINWEB%.DanielAugot, %MAINWEB%.LudovicPerret

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA