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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-13 [2011/07/12 19:26] (current)
Line 1: Line 1:
 +
 +===== Codes correcteurs d'erreurs, calcul formel: applications à la cryptologie (48h, 6 ECTS) =====
 +
 +Responsables : [[http://www.grobner.org/jcf/index.html|Jean-Charles Faugère]] et Jean-Pierre Tillich
 +
 +==== Intervenants  2008-2009  ====
 +<dd>
 +   * [[http://www.grobner.org/jcf/index.html|Jean-Charles Faugère]]:  systèmes d'équations algébriques, leur résolution efficace.
 +   * Ludovic Perret: Applications en Cryptographie.
 +   * [[http://www-rocq.inria.fr/~augot|Daniel Augot]]: théorie algébrique des codes.
 +   * [[www-rocq.inria.fr/who/Nicolas.Sendrier/|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 codes//s'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="Planning//2008//2009"> ]] 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&eacute;n&eacute;rale</TD>
 +   <TD noWrap align=3Dmiddle>L. Perret </span>, Jean-Pierre Tillich</TD>
 +   <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI0.pdf|Introduction GB et Crypto]] </TD>
 +  </TR>
 + <P>
 +  <TR>
 + <TD noWrap align=3Dmiddle>25/09/2008</TD>
 + <TD noWrap align=3Dmiddle>Introduction &agrave; la cryptographie multivari&eacute;e.  
 + Introduction aux bases de Grobner </TD>
 + <TD noWrap align=3Dmiddle>L. Perret</TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI1.pdf|Cryptographie multivari&eacute;e]]
 + [[http://fgbrs.grobner.org/@papers/cours//MPRI//gb.pdf|Introduction aux GB ]]</TD>
 +  </TR>
 +<P>
 +  <TR>
 + <TD noWrap align=3Dmiddle>02/10/2008</TD>
 + <TD noWrap align=3Dmiddle>Principe de la cryptanalyse alg&eacute;brique. 
 + Cryptanalyse de HFE et IP. </TD>
 + <TD noWrap align=3Dmiddle>L. Perret</TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI2.pdf|Cryptanalyse alg&eacute;brique]] </TD>
 +  </TR>
 +  
 +<P>
 + <TR>
 + <TD noWrap align=3Dmiddle>09/10/2008</TD>
 + <TD noWrap align=3Dmiddle>Bases de Gr&ouml;bner
 + Id&eacute;al, Vari&eacute;t&eacute;s.  </TD>
 + <TD noWrap align=3Dmiddle><span class="Style18">L. Perret </span></TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI3.pdf|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">[[http://www.grobner.org/jcf/index.html|JC Faug&egrave;re]]</span></TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI4.pdf|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">[[http://www.grobner.org/jcf/index.html|JC Faug&egrave;re]]</span></TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI5.pdf|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">[[http://www.grobner.org/jcf/index.html|JC Faug&egrave;re]]</span></TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI6.pdf|Algorithme F4]]</TD>
 +  </TR>
 +  <TR>
 + <TD noWrap align=3Dmiddle>13/11/2008</TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/MPRI//partiel//2008.pdf| devoir a la maison]]
 + + questions.
 + Algorithme F5 + Complexite</TD>
 + <TD noWrap align=3Dmiddle><span class="Style18">[[http://www.grobner.org/jcf/index.html|JC Faug&egrave;re]]</span></TD>
 + <TD noWrap align=3Dmiddle>[[http://fgbrs.grobner.org/@papers/cours_MPRI7.pdf| 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&eacute;or&egrave;me de Shannon
 + </TD>
 + <TD noWrap align=3Dmiddle><span class="Style18">[[http://www-rocq.inria.fr/secret/Jean-Pierre.Tillich/index.html|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&eacute;or&egrave;me de Shannon (suite et fin)
 +bornes sur la distance minimale d'un code
 + </TD>
 + <TD noWrap align=3Dmiddle><span class="Style18">[[http://www-rocq.inria.fr/secret/Jean-Pierre.Tillich/index.html|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 [[http://theory.lcs.mit.edu/~madhu/FT04/|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 ====
 +
 +[[http://mpri.master.univ-paris7.fr/C-2-12.html|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.
 +
 +[[http://mpri.master.univ-paris7.fr/C-2-22.html|2.22 Algorithmes efficaces en calcul formel]]. Pour ceux qui veulent voir d'autres aspects du calcul formel.
 +
 +==== Stages/internships ====
 +
 +(mise a jour le**21 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>  [[http://fgbrs.grobner.org/@papers/sujet_optimisation.pdf| Optimisation algebrique sous contraintes et calcul formel]].
 +<li>  [[http://fgbrs.grobner.org/@papers/sujet_geometry.pdf| Solutions reelles des systemes polynomiaux : calcul d'invariants geometriques]].
 +</ul>
 +Stages proposés par l'UCL (Louvain en Belgique)
 +<ul>
 +<li>[[http://www-rocq.inria.fr/secret/Daniel.Augot/internship//UCL//Belgium.pdf|quatre sujets]]
 +</ul>
 +Stages proposés dans l'entreprise  Oberthur Card Systems
 +<ul>
 +<li>[[http://www-rocq.inria.fr/secret/Daniel.Augot/Internship-Oberthur-hash.pdf|Fonctions de Hachage]]</li>
 +<li>[[http://www-rocq.inria.fr/secret/Daniel.Augot/Internship-Oberthur-FaultAttacks.pdf|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 ====
 +   * [[2009-2010-C-2-13|Année 2009-2010]]
 +   * [[2008-2009-C-2-13|Année 2008-2009]]
 +   * [[2007-2008-C-2-13|Année 2007-2008]]
 +   * [[2006-2007-C-2-13|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