Polynomial equivalence problems and applications to multivariate cryptosystems

Françoise Levy-Dit-Vehel (1) , Ludovic Perret (1)

1 CODES - Coding and cryptography

At Eurocrypt'96, J.Patarin proposed a signature and authentication scheme whose security relies on the difficulty of the Isomorphism of Polynomials problem . In this paper, we study a variant of this problem, namely the Isomorphism of Polynomials with one secret problem and we propose new algorithms to solve it, which improve on all the previously known algorithms. As a consequence, we prove that, when the number of polynomials (u) is close to the number of variables (n), the instances considered in and can be broken. We point out that the case n-u small is the most relevant one for cryptographic applications. Besides, we show that a large class of instances that have been presumed difficult in and can be solved in deterministic polynomial time. We also give numerical results to illustrate our methods.

Mots clés: MULTIVARIATE POLYNOMIAL EQUATIONS; ISOMORPHISM OF POLYNOMIALS; GRöBNER BASES

Domaines: Autre [cs.OH]

Françoise Levy-Dit-Vehel, Ludovic Perret. Polynomial equivalence problems and applications to multivariate cryptosystems. [Research Report] RR-5119, INRIA. 2004. ⟨inria-00071464⟩