Cryptology ePrint Archive: Report 2009/583

Differential-Algebraic Algorithms for the Isomorphism of Polynomials Problem

Charles Bouillaguet and Jean-Charles Faugère and Pierre-Alain 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 well-known 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\"obner bases and statistical tools such as the birthday paradox and a totally new object in the IP-context, the so-called \emph{Galton-Watson 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 public-key schemes.

Category / Keywords: public-key cryptography / cryptanalysis, HFE, Groebner Bases, Isomorphism of Polynomials

Date: received 16 Nov 2009, last revised 19 Feb 2010

Contact author: charles bouillaguet at ens fr

Available format(s): PDF | BibTeX Citation

Note: Update version with new algorithms.

Version: 20100219:134212 (All versions of this report)

Short URL: ia.cr/2009/583