@inbook{a4279c80a0ae4a908a49cfb88ad0bb36,
title = "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 [P]. 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 [P] and [P1] 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 [P] and [P1] can be solved in deterministic polynomial time. We also give numerical results to illustrate our methods.",
keywords = "Gr{\"o}bner Bases, Isomorphism of Polynomials, Multivariate polynomial equations",
author = "Fran{\c c}oise Levy-dit-Vehel and Ludovic Perret",
year = "2003",
month = jan,
day = "1",
doi = "10.1007/978-3-540-24582-7\_18",
language = "English",
isbn = "3540206094",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "235--251",
editor = "Thomas Johansson and Subhamoy Maitra",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}