Supervision : Jean-Charles FAUGÈRE

Co-supervision : SAFEY EL DIN Mohab

Solving multihomogeneous and determinantal systems Algorithms - Complexity - Applications

Multivariate polynomial systems arising in Engineering Science often carry algebraic structures related to the problems they stem from. In particular, multi-homogeneous, determinantal structures and boolean systems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis of the ideal associated to the system. This thesis provides new tools for solving such structured systems in the context of Gröbner basis algorithms.
On the one hand, these tools bring forth new bounds on the complexity of the computation of Gröbner bases of several families of structured systems (bilinear systems, determinantal systems, critical point systems, boolean systems). In particular, it allows the identification of families of systems for which the complexity of the computation is polynomial in the number of solutions.
On the other hand, this thesis provides new algorithms which take profit of these algebraic structures for improving the efficiency of the Gröbner basis computation and of the whole solving process (multi-homogeneous systems, boolean systems). These results are illustrated by applications in cryptology (cryptanalysis of MinRank), in optimization and in effective real geometry (critical point systems).

2009-2016 Publications

• 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”, thesis, phd defence 10/09/2012, supervision Faugère, Jean-Charles, co-supervision : 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)