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?

Here we show that at least in certain special cases there is a polynomial-time randomized algorithm for determining this equivalence, if it exists. Specifically, we give randomized polynomial-time algorithms for determining equivalence to the power symmetric polynomials and to the elementary symmetric polynomial. As an application, we show that if in the key generation phase of Patarin’s authentication scheme (which is based on the presumed hardness of the polynomial equivalence problem), a random multilinear polynomial is used to generate the secret, then the scheme can be broken and the secret recovered in randomized polynomial-time.