TY - CHAP
T1 - Polynomial equivalence problems and applications to multivariate cryptosystems
AU - Levy-dit-Vehel, Françoise
AU - Perret, Ludovic
PY - 2003/1/1
Y1 - 2003/1/1
N2 - 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.
AB - 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.
KW - Gröbner Bases
KW - Isomorphism of Polynomials
KW - Multivariate polynomial equations
UR - https://www.scopus.com/pages/publications/0346265015
U2 - 10.1007/978-3-540-24582-7_18
DO - 10.1007/978-3-540-24582-7_18
M3 - Chapter
AN - SCOPUS:0346265015
SN - 3540206094
SN - 9783540206095
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 235
EP - 251
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Johansson, Thomas
A2 - Maitra, Subhamoy
PB - Springer Verlag
ER -