**Graph-Theoretic Algorithms for the ``Isomorphism of Polynomials'' Problem**

*Charles Bouillaguet and Pierre-Alain Fouque and Amandine Véber*

**Abstract: ** We give three new algorithms to solve the ``isomorphism of
polynomial'' problem, which was underlying the hardness of
recovering the secret-key in some multivariate trapdoor one-way
functions. In this problem, the adversary is given two quadratic
functions, with the promise that they are equal up to linear changes
of coordinates. Her objective is to compute these changes of
coordinates, a task which is known to be harder than
Graph-Isomorphism. Our new algorithm build on previous work in a
novel way. Exploiting the birthday paradox, we break instances of
the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$
(heuristically), where $q^n$ is the time needed to invert the
quadratic trapdoor function by exhaustive search. These results are
obtained by turning the algebraic problem into a combinatorial one,
namely that of recovering partial information on an isomorphism
between two exponentially large graphs. These graphs, derived from
the quadratic functions, are new tools in multivariate cryptanalysis.

**Category / Keywords: **public-key cryptography /

**Date: **received 26 Oct 2012

**Contact author: **charles bouillaguet at lifl fr, pierre-alain fouque@ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20121029:140614 (All versions of this report)

**Short URL: **ia.cr/2012/607

[ Cryptology ePrint archive ]