Name
Abstract | ||
|---|---|---|
We consider the following computational problem. Let F be a field. Given two n-variate polynomials f(x1,.., xn) and g(x1,.., xn) 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 xi's for each xj 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133144 | SODA |
Keywords | Field | DocType |
linear combination,special case,field f,polynomial g,n-variate polynomial,graph isomorphism problem,cryptographic authentication scheme,polynomial equivalence problem,invertible linear transformation,input polynomial,authentication scheme,following computational problem,efficient algorithm,graph isomorphism,linear transformation,randomized algorithm,polynomial time | Randomized algorithm,Linear combination,Discrete mathematics,Computational problem,Combinatorics,Polynomial,Minimal polynomial (field theory),Algorithm,Equivalence (measure theory),Invertible matrix,Mathematics,Graph isomorphism problem | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 3 | 0.38 |
References | Authors | |
5 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |