New Insight into the Isomorphism of Polynomial Problem IP1S and Its Use in Cryptography

Gilles Macario-Rat, Jérôme Plût, Henri Gilbert

Abstract

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 Gröbner basis computation.