### Differential-Algebraic Algorithms for the Isomorphism of Polynomials Problem

Charles Bouillaguet, Jean-Charles Faugère, 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öbner 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.

Note: Update version with new algorithms.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysisHFEGroebner BasesIsomorphism of Polynomials
Contact author(s)
charles bouillaguet @ ens fr
History
2010-02-19: revised
See all versions
Short URL
https://ia.cr/2009/583 CC BY

BibTeX

@misc{cryptoeprint:2009/583,
author = {Charles Bouillaguet and Jean-Charles  Faugère and Pierre-Alain Fouque and Ludovic Perret},
title = {Differential-Algebraic 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}
} Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.