## IACR paper details

Title | A New Efficient Algorithm for Solving Systems of Multivariate Polynomial Equations |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2005 |
---|

URL | http://eprint.iacr.org/2005/312 |
---|

Author | Xijin Tang |
---|

Author | 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\"{o}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. |
---|

Search for the paper

@misc{eprint-2005-12646,
title={A New Efficient Algorithm for Solving Systems of Multivariate Polynomial Equations},
booktitle={IACR Eprint archive},
keywords={multivariate cryptography, cryptography,polynomial equations over finite field, algebraic attack, Dixon Resultants, DR.},
url={http://eprint.iacr.org/2005/312},
note={ tangxij@mails.gucas.ac.cn 13032 received 5 Sep 2005},
author={Xijin Tang and Yong Feng},
year=2005
}

Download a complete BibTeX file.