Paper 2012/607

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

Charles Bouillaguet, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
charles bouillaguet @ lifl fr
pierre-alain fouque @ ens fr
History
2012-10-29: received
Short URL
https://ia.cr/2012/607
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/607,
      author = {Charles Bouillaguet and Pierre-Alain Fouque and Amandine Véber},
      title = {Graph-Theoretic Algorithms for the ``Isomorphism of Polynomials'' Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2012/607},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/607}},
      url = {https://eprint.iacr.org/2012/607}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.