Polynomial-time algorithms for quadratic isomorphism of polynomials: The regular case

Let f=(f1,…,fm) and g=(g1,…,gm) be two sets of m≥1m≥1 nonlinear polynomials in K[x1,…,xn]K[x1,…,xn] (KK being a field). We consider the computational problem of finding–if any–an invertible transformation on the variables mapping f to g. The corresponding equivalence problem is known as Isomorphism of Polynomials with one Secret (IP1S) and is a fundamental problem in multivariate cryptography. Amongst its applications, we can cite Graph Isomorphism (GI) which reduces to equivalence of cubic polynomials with respect to an invertible linear change of variables, according to Agrawal and Saxena. The main result is a randomized polynomial-time algorithm for solving IP1S for quadratic instances–a particular case of importance in cryptography.To this end, we show that IP1S for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory. We show that we can essentially linearize the problem by reducing quadratic-IP1S to test the orthogonal simultaneous similarity of symmetric matrices; this latter problem was shown by Chistov, Ivanyos and Karpinski (ISSAC 1997) to be equivalent to finding an invertible matrix in the linear space Kn×nKn×n of n×nn×n matrices over KK and to compute the square root in a certain representation in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing a representation of the square root of a matrix in Kn×nKn×n, for various fields (including finite fields), as a product of two matrices. Each coefficient of these matrices lies in an extension field of KK of polynomial degree. We then consider #IP1S, the counting version of IP1S for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the more general Isomorphism of Polynomials (IP) problem where we allow an invertible linear transformation on the variables and on the set of polynomials. A randomized polynomial-time algorithm for solving IP when f=(x1d,…,xnd) is presented. From an algorithmic point of view, the problem boils down to factoring the determinant of a linear matrix (i.e.  a matrix whose components are linear polynomials). This extends to IP a result of Kayal obtained for PolyProj.