Paper 2009/583
DifferentialAlgebraic Algorithms for the Isomorphism of Polynomials Problem
Charles Bouillaguet, JeanCharles Faugère, PierreAlain Fouque, and Ludovic Perret
Abstract
In this paper, we investigate the difficulty of the Isomorphism of Polynomials (IP) Problem as well as one of its variant IP1S. The Isomorphism of Polynomials is a wellknown problem studied more particularly in multivariate cryptography as it is related to the hardness of the key recovery of such cryptosystems. The problem is the following: given two families of multivariate polynomials~$\A$ and~$\B$, find two invertible linear (or affine) mappings $S$ and $T$ such that $\B=T\circ \A \circ S$. For IP1S, we suppose that $T$ is the identity. It is known that the difficulty of such problems depends on the structure of the polynomials (\ie homogeneous, or not) and the nature of the transformations (affine, or linear). Here, we analyze the different cases and propose improved algorithms. We precisely describe the situation in terms of complexity and sufficient conditions to make the algorithms work. The algorithms presented here combine linear algebra techniques, including the use of differentials, together with Gröbner bases and statistical tools such as the birthday paradox and a totally new object in the IPcontext, the socalled \emph{GaltonWatson trees}. We show that random instances of IP1S with quadratic polynomials can be broken in time $\bigO{n^6}$, where $n$ is the number of variables, independently of the number of polynomials. For IP1S with cubic polynomials, as well as for IP, we propose new algorithms of complexity $\bigO{n^6}$ if the polynomials of $\A$ are inhomogeneous and $S, T$ linear. In all the other cases, we propose an algorithm that requires $\bigO{n^6 \cdot q^{n/2}}$ computation. Finally, we propose several algorithms for different subcases of the full IP problem, the best of which has complexity $\bigO{q^{n/2}}$. These new tools allow to break the challenges proposed by Patarin in practice, and also raise some fundamental questions about the general security of multivariate publickey schemes.
Note: Update version with new algorithms.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 cryptanalysisHFEGroebner BasesIsomorphism of Polynomials
 Contact author(s)
 charles bouillaguet @ ens fr
 History
 20100219: revised
 20091201: received
 See all versions
 Short URL
 https://ia.cr/2009/583
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/583, author = {Charles Bouillaguet and JeanCharles Faugère and PierreAlain Fouque and Ludovic Perret}, title = {DifferentialAlgebraic Algorithms for the Isomorphism of Polynomials Problem}, howpublished = {Cryptology ePrint Archive, Paper 2009/583}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/583}}, url = {https://eprint.iacr.org/2009/583} }