by presenting a randomized polynomial-time algorithm for solving simultaneous equivalence of quadratic forms over various fields.

Equivalence of multivariate polynomials is also a fundamental problem in Multivariate Public-Key Cryptography ([`MPKC`]{}). This is a family of asymmetric (encryption and signature) schemes whose public-key is given by a set of $m$ multivariate equations ([@C*; @DBLP:conf/eurocrypt/Patarin96]). To minimize the public-key storage, the multivariate polynomials considered are usually quadratic. The basic idea of [`MPKC`]{}is to construct a public-key which is equivalent to a set of quadratic multivariate polynomials with a specific structure (see for instance [@WP11]). Note that the notion of equivalence considered in this context is more general than the one considered for [`PolyEquiv`]{}or [`IP1S`]{}. Indeed, the equivalence is induced by an invertible linear change of variables and an invertible linear combination on the polynomials. The corresponding equivalence problem is known ([@DBLP:conf/eurocrypt/Patarin96]) as *Isomorphism of Polynomials* ([`IP`]{}or `IP2S`).

[`PolyEquiv`]{}, [`IP`]{}, and [`IP1S`]{}are not NP-Hard unless the polynomial-hierarchy collapses, [@DBLP:journals/eccc/ECCC-TR04-116; @DBLP:conf/eurocrypt/PatarinGC98]. However, the situation changes drastically when considering the equivalence for more general linear transformations (in particular, not necessarily invertible). In this context, the problem is called [`PolyProj`]{}. At [ SODA’11]{}, [@Kayal2011] showed that [`PolyProj`]{}is NP-Hard. This may be due to the fact that 