Journal papers

• A Quadratically Convergent Algorithm for Structured Low-Rank Approximation.
  With Eric Schost.
  Foundations of Computational Mathematics. 1-36, 2015.
  Arxiv. Maple code.
• Exact Solutions in Structured Low-Rank Approximation.
  With Giorgio Ottaviani and Bernd Sturmfels.
  SIAM Journal on Matrix Analysis and Applications. 35(4):1521-1542, 2014.
  [pdf] [bib].
• On the Complexity of Computing Critical Points with Gröbner Bases.
  SIAM Journal on Optimization. 24(3):1382-1401, 2014.
  [pdf] [bib] abstract.

  ---

  Abstract: Computing the critical points of a polynomial function $q\in\Q[X_1,\ldots,X_n]$ restricted to the vanishing locus $V\subset\R^n$ of polynomials $f_1,\ldots, f_p\in\Q[X_1,\ldots, X_n]$ is of first importance in several applications in optimization and in real algebraic geometry. These points are solutions of a highly structured system of multivariate polynomial equations involving maximal minors of a Jacobian matrix. We investigate the complexity of solving this problem by using Gr\"obner basis algorithms under genericity assumptions on the coefficients of the input polynomials. The main results refine known complexity bounds (which depend on the maximum $D=\max(\deg(f_1),\ldots,\deg(f_p),\deg(q))$) to bounds which depend on the list $(\deg(f_1),\ldots,\deg(f_p),\deg(q))$: we prove that the Gr\"obner basis computation can be performed in $\delta^{O(\log(A)/\log(G))}$ arithmetic operations in $\Q$, where $\delta$ is the algebraic degree of the ideal vanishing on the critical points, and $A$ and $G$ are the arithmetic and geometric average of a multiset constructed from the sequence of degrees. As a by-product, we prove that solving such generic optimization problems with Gr\"obner bases requires at most $D^{O(n)}$ arithmetic operations in $\Q$, which meets the best known complexity bound for this problem. Finally, we illustrate these complexity results with experiments, giving evidence that these bounds are relevant for applications.

  ---

• On the Complexity of the Generalized MinRank Problem.
  With Jean-Charles Faugère, Mohab Safey El Din.
  Journal of Symbolic Computation. 55:30-58, 2013.
  [pdf] [bib] abstract.

  ---

  Abstract: We study the complexity of solving the \emph{generalized MinRank problem}, i.e. computing the set of points where the evaluation of a polynomial matrix has rank at most $r$. A natural algebraic representation of this problem gives rise to a \emph{determinantal ideal}: the ideal generated by all minors of size $r+1$ of the matrix. We give new complexity bounds for solving this problem using Gr\"obner bases algorithms under genericity assumptions on the input matrix. In particular, these complexity bounds allow us to identify families of generalized MinRank problems for which the arithmetic complexity of the solving process is polynomial in the number of solutions. We also provide an algorithm to compute a rational parametrization of the variety of a 0-dimensional and radical system of bi-degree $(D,1)$. We show that its complexity can be bounded by using the complexity bounds for the generalized MinRank problem.

  ---

• On the Complexity of Solving Quadratic Boolean Systems.
  With Magali Bardet, Jean-Charles Faugère, Bruno Salvy.
  Journal of Complexity, 29(1):53-75, 2013.
  [pdf] [bib] abstract.

  ---

  Abstract: A fundamental problem in computer science is to find all the common zeroes of $m$ quadratic polynomials in $n$ unknowns over $\mathbb{F}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in $4\log_2 n\,2^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. Under precise algebraic assumptions, we show that the deterministic variant of our algorithm has complexity bounded by $O(2^{0.841n})$ when $m=n$, while a probabilistic variant of the Las Vegas type has expected complexity $O(2^{0.792n})$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to~1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as~200, and thus very relevant for cryptographic applications.

  ---

• Gröbner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity.
  With Jean-Charles Faugère, Mohab Safey El Din.
  Journal of Symbolic Computation, 46(4):406-437, 2011.
  [pdf] [bib] Magma Code abstract.

  ---

  Abstract: Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gröbner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons of this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree (1,1)). Our goal is to provide a theoretical explanation of the aforementioned experimental behaviour and to propose new techniques to speed up the Gröbner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical F₅ criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. We propose also a variant of the F₅ Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous F₅ Algorithm. Lastly, we investigate the complexity of computing a Gröbner basis for the grevlex ordering of a generic 0-dimensional affine bilinear system over k[x₁,..., x_nx, y₁,..., y_ny]. In particular, we show that this complexity is upper bounded by O(binomial(n_x+n_y+min(n_x+1,n_y+1),min(n_x+1,n_y+1))^ω), which is polynomial in n_x+n_y (i.e. the number of unknowns) when min(n_x,n_y) is constant.

  ---

Articles in conference proceedings

• Sparse Gröbner Bases: the Unmixed Case.
  With Jean-Charles Faugère, Jules Svartz.
  Proceedings of the International Symposium on Symbolic and Algebraic Computation 2014 (ISSAC 2014).
  Held in Kobe, Japan.
  Arxiv.
• Critical Points and Gröbner Bases: the Unmixed Case.
  With Jean-Charles Faugère, Mohab Safey El Din.
  Proceedings of the International Symposium on Symbolic and Algebraic Computation 2012 (ISSAC 2012).
  Held in Grenoble, France.
  [pdf] [bib]
• Computing Loci of Rank Defects of Linear Matrices using Gröbner Bases and Applications to Cryptology.
  With Jean-Charles Faugère, Mohab Safey El Din.
  Proceedings of the International Symposium on Symbolic and Algebraic Computation 2010 (ISSAC 2010).
  Held in Munich, Germany.
  Distinguished Student Author Award.
  [pdf] [bib] slides abstract.

  ---

  Abstract: Computing loci of rank defects of linear matrices (also called the MinRank problem) is a fundamental NP-hard problem of linear algebra which has applications in Cryptology, in Error Correcting Codes and in Geometry. Given a square linear matrix (i.e. a matrix whose entries are k-variate linear forms) of size n and an integer r, the problem is to find points such that the evaluation of the matrix has rank less than r+1. The aim of the paper is to obtain the most efficient algorithm to solve this problem. To this end, we give the theoretical and practical complexity of computing Gröbner bases of two algebraic formulations of the MinRank problem. Both modelings lead to structured algebraic systems.

  The first modeling, proposed by Kipnis and Shamir generates bi-homogeneous equations of bi-degree (1,1). The second one is classically obtained by the vanishing of the (r+1)-minors of the given matrix, giving rise to a determinantal ideal. In both cases, under genericity assumptions on the entries of the considered matrix, we give new bounds on the degree of regularity of the considered ideal which allows us to estimate the complexity of the whole Gröbner bases computations. For instance, the exact degree of regularity of the determinantal ideal formulation of a generic well-defined MinRank problem is r(n-r)+1. We also give optimal degree bounds of the loci of rank defect which are reached under genericity assumptions; the new bounds are much lower than the standard multi-homogeneous Bézout bounds (or mixed volume of Newton polytopes).

  As a by-product, we prove that the generic MinRank problem could be solved in polynomial time in n (when n-r is fixed) as announced in a previous paper of Faugère, Levy-dit-Vehel and Perret. Moreover, using the determinantal ideal formulation, these results are used to break a cryptographic challenge (which was untractable so far) and allow us to evaluate precisely the security of the cryptosystem w.r.t. n, r and k. Our practical results suggest that, up to the software state of the art, this latter formulation is more adapted in the context of Gröbner bases computations.

  ---

• Algebraic Cryptanalysis of the PKC'09 Algebraic Surface Cryptosystem.
  With Jean-Charles Faugère.
  Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography (PKC 2010).
  Held in Paris, France.
  [pdf] [bib] slides Magma Code abstract.

  ---

  Abstract: In this paper, we fully break the Algebraic Surface Cryptosystem (ASC for short) proposed at PKC2009. This system is based on an unusual problem in multivariate cryptography: the Section Finding Problem. Given an algebraic surface X(x,y,t)∈F_p[x,y,t] such that deg_xy X(x,y,t)= w, the question is to find a pair of polynomials of degree d, u_x(t) and u_y(t), such that X(u_x(t),u_y(t),t)=0. In ASC, the public key is the surface, and the secret key is the section. This asymmetric encryption scheme enjoys reasonable sizes of the keys: for recommended parameters, the size of the secret key is only 102 bits and the size of the public key is 500 bits. In this paper, we propose a message recovery attack whose complexity is quasi-linear in the size of the secret key. The main idea of this algebraic attack is to decompose ideals deduced from the ciphertext in order to avoid to solve the section finding problem. Experimental results show that we can break the cipher for recommended parameters (the security level is 2¹⁰²) in 0.05 seconds. Furthermore, the attack still applies even when the secret key is very large (more than 10000 bits). The complexity of the attack is Õ(w⁷ d log(p)) which is polynomial with respect to all security parameters. In particular, it is quasi-linear in the size of the secret key which is (2 d+2) log(p). This result is rather surprising since the algebraic attack is often more efficient than the legal decryption algorithm.

  ---

Preprints

• Sparse polynomial systems with many positive solutions from bipartite simplicial complexes.
  With Frédéric Bihan. Submitted. Arxiv.

In the pipe

• Critical points computations on smooth varieties: degree and complexity bounds.
  With Mohab Safey El Din.
• Computing small certificates of inconsistency of quadratic fewnomial systems.
  With Jean-Charles Faugère and Jules Svartz.

Ph.D. thesis

• Solving multi-homogeneous and determinantal systems.
  Algorithms - Complexity - Applications.
  Supervisors: Jean-Charles Faugère, Mohab Safey El Din.
  PolSys project-team (INRIA/UPMC/LIP6).
  Université Pierre et Marie Curie, 2012.
  [pdf][bib]

Posters

• Newton-like Iteration for Determinantal Systems and Structured Low-Rank Approximation.
  Eric Schost, Pierre-Jean Spaenlehauer.
  International Symposium on Symbolic and Algebraic Computation 2013 (ISSAC 2013).
  Held in Boston, USA.
  abstract[pdf]. Maple code.

Talks in workshops and conferences

• Sparse polynomial systems with many positive solutions from bipartite simplicial complexes.
  • Workshop on Algebra, Geometry and Proofs in Symbolic Computation. Fields Institute, Toronto, Canada. December 7-16, 2015.
• A quadratically convergent algorithm for Structured Low-Rank Approximation.
  
  • ICIAM 2015, Workshop on hybrid methodologies for symbolic-numeric computations, Beijing, China, August 10-13, 2015.
  • RAIM 2013. Institut Henri Poincaré, Paris, France. November 18-20, 2013.
  • Numerical methods and computations. CIRM, Luminy, France. October 28-31, 2013.
• Exact solutions in structured low-rank approximation.
  
  • SIAM Conference on Applied Algebraic Geometry. Daejeon, Korea, August 3-7, 2015. Minisymposium on ML Degree and Critical Points.
  • SLRA workshop. Grenoble, France. June, 1, 2015.
• Sparse Gröbner bases: the unmixed case.
  
  • SIAM Conference on Applied Algebraic Geometry. Daejeon, Korea, August 3-7, 2015. Minisymposium on Algorithms and Complexity in Polynomial Systems.
  • Conference on Effective Moduli Spaces and Applications to Cryptology. Rennes, France. June, 12, 2014.
• Gröbner bases and bilinear systems.
  DLP 2014. Ascona, Switzerland. May, 06, 2014.
• Solving Determinantal and Quadratic Boolean Systems. Applications to Algebraic Cryptanalysis.
  Journées C2 2014. Grenoble, France. March, 26, 2014.
  slides[pdf]
  
• Critical Points and Gröbner Bases: the Mixed Case.
  • Workshop on Gröbner Bases, Resultants and Linear Algebra. RISC, Hagenberg, Austria. September 3-6, 2013.
  • SIAM Conference on Applied Algebraic Geometry. Fort Collins, CO, USA. August 1-4, 2013. Mini-Symposium on Algorithms in Real Algebraic Geometry.
• Critical Points and Gröbner Bases: the Unmixed Case.
  ISSAC 2012. Grenoble, France. July 22-25, 2012.
• On the Complexity of Solving Boolean Quadratic Systems.
  SIAM Conference on Applied Algebraic Geometry. Raleigh, NC, USA. October 6-9, 2011. Mini-Symposium on Algebraic Complexity.
• Gröbner bases of Structured Systems and their Applications in Cryptology.
  MAYA Workshop 2011. Bochum, Germany. July 28-29, 2011.
  slides[pdf]
  
• Computing Loci of Rank Defects of Linear Matrices using Gröbner Bases and Applications to Cryptology.
  ISSAC 2010. Munich, Germany. July 25-28, 2010.
  slides[pdf]
  
• Algebraic Cryptanalysis of the PKC'09 Algebraic Surface Cryptosystem.
  PKC 2010. Paris, France. May 26-28, 2010.
  slides[pdf]
  
• Algebraic-Differential Cryptanalysis of DES.
  Weworc 2009. Graz, Austria. July 7-9, 2009.
  summary[pdf] slides[pdf]
  

Talks in seminars

• Sparse polynomial systems with many positive solutions from bipartite simplicial complexes.
  • Journées Nationales du Calcul Formel. Cluny, France, Nov. 2-6, 2015.
• On the complexity of computing critical points with Gröbner bases.
  • University of Neuchatel, Switzerland. 12/08, 2014.
• Sparse Gröbner bases: the unmixed case
  • LIRMM, Montpellier, France. 03/04, 2015.
  • Séminaire de géométrie, LAMA. Chambéry, France. 12/12, 2014.
  • Western University, CS department. London, Ontario, Canada. 06/04, 2014.
• A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation.
  • Séminaire de Calcul Formel. Rennes, France. 11/28, 2014.
  • Séminaire Caramel. Nancy, France. 03/13, 2014.
  • Séminaire Calcul Formel. Limoges, France. 03/06, 2014.
  • Séminaire SpecFun. Palaiseau, France. 03/03, 2014.
  • Séminaire ARIC. Lyon, France. 02/27, 2014.
• Critical Points, Gröbner Bases and Structured Low Rank Approximation.
  • Technische Universiteit. Eindhoven, Netherlands. 12/11, 2013.
  • Dipartimento di Matematica e Informatica U. Dini. Florence, Italy. 10/23, 2013.
• A quadratically convergent algorithm for Structured Low-Rank Approximation.
  
  • Séminaire PolSys. LIP6/UPMC/INRIA, Paris, France. 09/27, 2013.
• Gröbner bases of Structured Systems and their Applications in Cryptology and in Geometry.
  
  • Séminaire Crypto. PrisM, UVSQ, Versailles, France. 01/09, 2013.
  • Séminaire CARAMEL. LORIA, Nancy, France. 01/17, 2013.
  • Séminaire Calcul Formel et Complexité. IRMAR, Rennes, France. 01/18, 2013.
  • SCPQ Webinar. 03/08, 2012.
• On the Complexity of Solving Boolean Quadratic Systems.
  
  • Séminaire ARIC. ENS Lyon, France. 10/11, 2012.
  • Journées Nationales du Calcul Formel. CIRM, Luminy, France. 11/17, 2011.
• Algebraic Cryptanalysis of the PKC'09 Algebraic Surface Cryptosystem.
  
  • Séminaire Cryptographie et Sécurité. PRISM/UVSQ, Versailles 04/28, 2011.
• Computing Critical Points with Gröbner Bases: Complexity and Applications to Polynomial Minimization.
  
  • Max Planck Institute for Mathematics. Bonn, Germany 07/29, 2013.
  • Séminaire Combinatoire et Algorithmes. LITIS, Rouen 02/23, 2012.
  • Séminaire Salsa. LIP6/UPMC/INRIA 12/09, 2011.
  • Séminaire Salsa. LIP6/UPMC/INRIA 02/11, 2011.
  • Séminaire Algorithms. INRIA Paris/Rocquencourt 01/31, 2011.
• Bilinear Systems and Determinantal Varieties. Application to MinRank.
  
  • Journées Codage et Cryptographie. Oléron 04/05, 2011.
  • Séminaire Cryptologie. Rennes 10/08, 2010.
  • Journées nationales du calcul formel. CIRM, Luminy 05/03, 2010. Summary[pdf].
• Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms, Complexity and Applications.
  
  • Séminaire Salsa: structured systems. LIP6/UPMC/INRIA 07/09, 2010.
  • Séminaire Algorithms. INRIA Paris/Rocquencourt 04/26, 2010. slides[pdf].
• Algebraic-Differential Cryptanalysis of DES.
  
  • Journées nationales "Codage et Cryptographie". Fréjus 10/05, 2009. slides[pdf].
  • Séminaire de Cryptologie. Caen 10/29, 2009. slides[pdf].
  • Séminaire SALSA. Paris 07/03, 2008.