We consider the following computational problem. Let F be a field. Given two
n-variate polynomials f(x_{1}, .. , x_{n}) and g(x_{1},
.. , 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.

}, author = {Neeraj Kayal}, booktitle = {Symposium on Discrete Algorithms (SODA)}, publisher = {Society for Industrial and Applied Mathematics}, title = {Efficient algorithms for some special cases of the polynomial equivalence problem}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=145651}, year = {2011}, }