Paper 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è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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysis
Contact author(s)
zhaoshangwei @ amss ac cn
History
2010-11-25: revised
2010-11-25: received
See all versions
Short URL
https://ia.cr/2010/604
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/604,
      author = {Shangwei Zhao and Ruyong Feng and Xiao-Shan Gao},
      title = {On Functional Decomposition of Multivariate Polynomials with  Differentiation and Homogenization},
      howpublished = {Cryptology ePrint Archive, Paper 2010/604},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/604}},
      url = {https://eprint.iacr.org/2010/604}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.