Cryptology ePrint Archive: Report 2010/604

On Functional Decomposition of Multivariate Polynomials with Differentiation and Homogenization

Shangwei Zhao,Ruyong Feng and Xiao-Shan Gao

Abstract: In this paper, we give a theoretical analysis for the algorithms to compute functional decomposition for multivariate polynomials based on differentiation and homogenization which are proposed by Ye, Dai, Lam (1999) and Faug\`{e}re, Perret (2006, 2008, 2009). We show that a degree proper functional decomposition for a set of randomly decomposable quartic homogenous polynomials can be computed using the algorithm with high probability. This solves a conjecture proposed by Ye, Dai, and Lam (1999). We also propose a conjecture such that the decomposition for a set of polynomials can be computed from that of its homogenization with high probability. Finally, we prove that the right decomposition factors for a set of polynomials can be computed from its right decomposition factor space. Combining these results together, we prove that the algorithm can compute a degree proper decomposition for a set of randomly decomposable quartic polynomials with probability one when the base field is of characteristic zero, and with probability close to one when the base field is a finite field with sufficiently large odd number under the assumption that the conjecture is correct.

Category / Keywords: public-key cryptography / cryptanalysis

Date: received 24 Nov 2010, last revised 24 Nov 2010

Contact author: zhaoshangwei at amss ac cn

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20101125:064352 (All versions of this report)

Discussion forum: Show discussion | Start new discussion