International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 29 October 2012

Charles Bouillaguet, Pierre-Alain Fouque, Amandine Véber
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.