Paper 2005/312

A New Efficient Algorithm for Solving Systems of Multivariate Polynomial Equations

Xijin Tang and Yong Feng

Abstract

The security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. The classical algorithm for solving such a system is Buchberger's algorithm for constructing Gröbner bases. Another algorithm for solving such a system is XL algorithm. For sparse system, Buchberger's algorithm benefits from sparsity of the system, but its complexity is impractical and hard to determine. XL could not make a good use of sparse structure of the system, since XL has no good strategy of choosing the multiply monomials. In this paper, based on Extended Dixon Resultants, a new algorithm DR is proposed to solve systems of multivariate polynomial equations. The basic idea of DR is to apply Extended Dixon Resultants method to system of multivariate polynomial equations, by taking $x_1 \ldots x_{n-1}$ as variables and $x_n$ as parameter. The time complexity of DR technique is evaluated, it seems to be polynomial when the system is sparse and $m=n$ and mixed volume is polynomial. As far as we know, it is the first algorithm which has better behavior than exhaustive search for some sparse systems over large field. Moreover, DR technique is compared with Buchberger's algorithm and XL technique in this paper. It is shown that DR is far more efficient than Buchberger's algorithm and XL when $m=n$. DR is a quite efficient algorithm, it makes a good use of the sparsity of the sparse system. Besides its efficiency, another advantage of DR is that its complexity is easy to determine.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
multivariate cryptographycryptographypolynomial equations over finite fieldalgebraic attackDixon ResultantsDR.
Contact author(s)
tangxij @ mails gucas ac cn
History
2005-09-12: received
Short URL
https://ia.cr/2005/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/312,
      author = {Xijin Tang and Yong Feng},
      title = {A New Efficient Algorithm for Solving Systems of Multivariate Polynomial Equations},
      howpublished = {Cryptology ePrint Archive, Paper 2005/312},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/312}},
      url = {https://eprint.iacr.org/2005/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.