Efficient algorithms for some special cases of the polynomial equivalence problem

Neeraj Kayal

2011

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.

PDF file |

In Symposium on Discrete Algorithms (SODA)

Publisher Society for Industrial and Applied Mathematics

SIAM

Type | Inproceedings |

> Publications > Efficient algorithms for some special cases of the polynomial equivalence problem