"Efficient Algorithm for Decomposing Multivariate Polynomials and its Applications to Cryptography "

Abstract
In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of an arbitrary degree. This problem, also known as the Functional Decomposition Problem} (FDP) is a classical problem in computer algebra. This the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). The method relies on the computation of the column ideal of the ideal generated by the partial derivatives of the polynomials obtained from the composition. This computation can be done efficiently using Gröbner bases. From the cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R$^{-}$ schemes, becomes useless. By the way, we believe that this algorithm might have application in the cryptanalysis of block-ciphers.

"PERRET Ludovic" is mentioned on: Home | Participants