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
[ Cryptology ePrint archive ]