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.

Publication type | Inproceedings |

Published in | Symposium on Discrete Algorithms (SODA) |

Publisher | Society for Industrial and Applied Mathematics SIAM |

- A super-polynomial lower bound for regular arithmetic formulas.
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- Lower bounds for depth three arithmetic circuits with small bottom fanin

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