HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:37:37 PM
Last modification on : Thursday, April 14, 2022 - 1:58:01 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