Supervision : Jean-Charles FAUGÈRE

Co-supervision : AUGOT Daniel

Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie

Les bases de Gröbner constituent un outil important pour la résolution de systèmes d'équations algébriques, et leur calcul est souvent la partie difficile de la résolution. Cette thèse est consacrée à des analyses de complexité de calculs de bases de Gröbner pour des systèmes surdéterminés (le nombre m d'équations est supérieur au nombre n d'inconnues).
Dans le cas générique ("aléatoire"), des outils existent pour analyser la complexité du calcul de base de Gröbner pour un système non surdéterminé (suites régulières, borne de Macaulay). Nous avons étendu ces résultats au cas surdéterminé, en définissant les suites semi-régulières et le degré de régularité dont nous donnons une analyse asymptotique précise. Par exemple dès que m>n nous gagnons un facteur 2 sur la borne de Macaulay, et un facteur 11,65 quand m=2n (ces facteurs se répercutent sur l'exposant de la complexité globale). Nous déterminons la complexité de l'algorithme F5 (Faugère) de calcul de base de Gröbner.
Ces résultats sont appliqués en protection de l'information, où les systèmes sont alors considérés modulo 2 : analyse de la complexité des attaques algébriques sur des cryptosystèmes, algorithmes de décodage des codes cycliques. Dans ce dernier cas, une remise en équation complète du problème conduit à utiliser des systèmes de dimension positive dont la résolution est de manière surprenante plus rapide. Nous obtenons ainsi un algorithme de décodage efficace de codes précedemment indécodables, permettant un décodage en liste et applicable à tout code cyclique.

2003-2015 Publications

• 2015
  • M. Bardet, J.‑Ch. Faugère, B. Salvy : “On the complexity of the F5 Gröbner basis algorithm”, Journal of Symbolic Computation, vol. 70, pp. 49-70, (Elsevier) (2015)
• 2013
  • M. Bardet, J.‑Ch. Faugère, B. Salvy, P.‑J. Spaenlehauer : “On the Complexity of Solving Quadratic Boolean Systems”, Journal of Complexity, vol. 29 (1), pp. 53-75, (Elsevier) (2013)
• 2009
  • D. Augot, M. Bardet, J.‑Ch. Faugère : “On the decoding of binary cyclic codes with the Newton’s identities”, Journal of Symbolic Computation, vol. 44 (12), Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics, pp. 1608-1625, (Elsevier) (2009)
• 2007
  • D. Augot, M. Bardet, J.‑Ch. Faugère : “On formulas for decoding binary cyclic codes”, IEEE International Symposium on Information Theory, 2007 (ISIT 2007), Nice, France, pp. 2646-2650, (IEEE) (2007)
• 2005
  • M. Bardet, J.‑Ch. Faugère, B. Salvy : “Asymptotic Behaviour of the Index of Regularity of Semi-Regular Quadratic Polynomial Systems”, MEGA 2005 - 8^th International Symposium on Effective Methods in Algebraic Geometry, Porto Conte, Alghero, Sardinia, Italy, pp. 1-17 (2005)
• 2004
  • M. Bardet : “Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie”, thesis, phd defence 12/08/2004, supervision Faugère, Jean-Charles, co-supervision : Augot, Daniel (2004)
  • J.‑Ch. Faugère, M. Bardet, B. Salvy : “On the complexity of Grbner basis computation of semi-regular overdetermined algebraic equations”, International Conference on Polynomial System Solving, Paris, France, pp. 71-75 (2004)
• 2003
  • D. Augot, M. Bardet, J.‑Ch. Faugère : “Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Grobner bases”, IEEE International Symposium on Information Theory - ISIT'2003, Yokohama, Japan, pp. 362-362, (IEEE Computer Society) (2003)
  • M. Bardet, J.‑Ch. Faugère, B. Salvy : “Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2”, (2003)