Direction de recherche : Jean-Charles FAUGÈRE

Co-encadrement : SAFEY EL DIN Mohab

Résolution de systèmes multi-homogènes et déterminantiels

De nombreux systèmes polynomiaux multivariés apparaissant en Sciences de l'Ingénieur possèdent une structure algébrique spécifique. En particulier, les structures multi-homogènes, déterminantielles et les systèmes booléens apparaissent dans une variété d'applications. Une méthode classique pour résoudre des systèmes polynomiaux passe par le calcul d'une base de Gröbner de l'idéal associé au système.
Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés.
D'une part, ces outils permettent d'obtenir sous des hypothèses de généricité des bornes de complexité du calcul de base de Gröbner de plusieurs familles de systèmes polynomiaux structurés (systèmes bilinéaires, systèmes déterminantiels, systèmes définissant des points critiques, systèmes booléens). Ceci permet d'identifier des familles de systèmes pour lequels la complexité arithmétique de résolution est polynomiale en le nombre de solutions.
D'autre part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité du calcul de base de Gröbner et de la résolution (systèmes multi-homogènes, systèmes booléens). Ces résultats sont illustrés par des applications concrètes en cryptologie (cryptanalyse des systèmes MinRank et ASC), en optimisation et en géométrie réelle effective (calcul de points critiques).

Publications 2009-2016

• 2016
  • J.‑Ch. Faugère, P.‑J. Spaenlehauer, J. Svartz : “Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems”, Proceedings of ISSAC 2016, Waterloo, Canada, pp. 223-230, (ACM) (2016)
  • M. Safey El Din, P.‑J. Spaenlehauer : “Critical Point Computations on Smooth Varieties: Degree and Complexity bounds”, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, pp. 183-190 (2016)
• 2014
  • J.‑Ch. Faugère, P.‑J. Spaenlehauer, J. Svartz : “Sparse Gröbner Bases: the Unmixed Case”, ISSAC 2014, Kobe, Japan (2014)
• 2013
  • J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “On the Complexity of the Generalized MinRank Problem”, Journal of Symbolic Computation, vol. 55, pp. 30-58, (Elsevier) (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)
• 2012
  • P.‑J. Spaenlehauer : “Solving multihomogeneous and determinantal systems Algorithms - Complexity - Applications”, soutenance de thèse, soutenance 09/10/2012, direction de recherche Faugère, Jean-Charles, co-encadrement : Safey, EL DIN Mohab (2012)
  • J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “Critical Points and Gröbner Bases: the Unmixed Case”, ISSAC 2012 - International Symposium on Symbolic and Algebraic Computation - 2012, Grenoble, France, pp. 162-169, (ACM) (2012)
• 2011
  • J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity”, Journal of Symbolic Computation, vol. 46 (4), pp. 406-437, (Elsevier) (2011)
• 2010
  • J.‑Ch. Faugère, M. Safey El Din, P.‑J. Spaenlehauer : “Computing Loci of Rank Defects of Linear Matrices using Gröbner Bases and Applications to Cryptology”, ISSAC 2010 - 35^th International Symposium on Symbolic and Algebraic Computation, Munich, Germany, pp. 257-264, (ACM) (2010)
  • J.‑Ch. Faugère, P.‑J. Spaenlehauer : “Algebraic Cryptanalysis of the PKC’09 Algebraic Surface Cryptosystem”, PKC 2010 - 13^th International Conference on Practice and Theory in Public Key Cryptography, vol. 6056, Lecture Notes in Computer Science, Paris, France, pp. 35-52, (Springer) (2010)
• 2009
  • J.‑Ch. Faugère, L. Perret, P.‑J. Spaenlehauer : “Algebraic-Differential Cryptanalysis of DES”, Western European Workshop on Research in Cryptology - WEWoRC 2009, Graz, Austria, pp. 1-5 (2009)