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
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
-
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}, url = {https://eprint.iacr.org/2005/312} }