New Insight into the Isomorphism of Polynomials problem IP1S and its Use in Cryptography
This paper investigates the mathematical structure of the "Isomorphism of Polynomial with One Secret" problem IP1S. Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable as first observed by Bouillaguet et al.. We show that the structure of the equations is directly linked to a matrix derived from the polar form of the polynomials. We prove that in the likely case where this matrix is cyclic, the problem can be solved in polynomial time --- using an algorithm that unlike previous solving techniques is not based upon Grobner basis computation.