An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography (Q733509)

The paper under review gives a new and general algorithm (any degree, any number of polynomials) for solving the Functional Decomposition Problem: given polynomials \(h_1, \dots, h_u\in K[x_1, \dots, x_n]\),\, finds new polynomials \(f_1, \dots , f_u, g_1, \dots , g_n\)\, such that \(h_i=f_i(g_1, \dots ,g_n )\). The method presented here improves to arbitrary degree a previous method of the authors [CRYPTO 2006, Lect. Notes Comput. Sci. 4117, 357--372 (2006; Zbl 1161.94397)] allowing to decompose polynomials of degree four. In the present paper the only restriction is that all the polynomials as supposed homogeneous of the same degree and the degrees of the wanted decomposition are given as input. Section 3 describes the proposed algorithm \textbf{MultivariateComPoly}. As usual the hardest task is to find the polynomials \(g_i\). To do this the algorithm find, using Gröbner bases of suitable ideals. the vector space \({\mathcal L}(g)=\mathrm{Span}(g_1,\dots , g_n)\). Then the polynomials \(f_1,\dots , f_u\)\, are determined solving a linear system of equations. Subsection 3.3.1 studies the complexity of \textbf{MultivariateComPoly}. This complexity depends of the degrees of the input and the ratio \(n/u\). In particular if \(\deg(f_i)=\deg(g_j)=2\),\, the complexity is \(O(n^{12})\)\, if \(u> \lfloor n/2\rfloor\)\, and \(O(n^9)\)\, if \(u=n\). As a by-product Section 4 shows that the two rounds \(2R^{-}\)\, schemes in multivariate Cryptography due to \textit{L. Goubin} and \textit{J. Patarin} [ICICS'97, Lect. Notes Comput. Sci. 1334, 369--380 (1997; Zbl 0903.94032)], become now insecure.