Skip to Main content Skip to Navigation

Polynomial equivalence problems and applications to multivariate cryptosystems

Abstract : 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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:37:37 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:16:41 PM


  • HAL Id : inria-00071464, version 1



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



Record views


Files downloads