Efficient algorithms for some special cases of the polynomial equivalence problem

We consider the following computational problem. Let F be a field. Given two n-variate polynomials f(x₁,., x_n) and g(x₁,., x_n) over the field F, is there an invertible linear transformation of the variables which sends f to g? In other words, can we substitute a linear combination of the x_i's for each x_j appearing in f and obtain the polynomial g? This problem is known to be at least as difficult as the graph isomorphism problem even for homogeneous degree three polynomials. There is even a cryptographic authentication scheme (Patarin, 1996) based on the presumed average-case hardness of this problem.

Here we show that at least in certain (interesting) special cases there is a polynomial-time randomized algorithm for determining this equivalence, if it exists. Somewhat surprisingly, the algorithms that we present are efficient even if the input polynomials are given as arithmetic circuits. As an application, we show that if in the key generation phase of Patarin's authentication scheme, a random multilinear polynomial is used to generate the secret, then the scheme can be broken and the secret recovered in randomized polynomial-time.