Details:
Title  Comparison Between XL and Gröbner Basis Algorithms  Author(s)  JeanCharles Faugère, Imai Hideki, Mitsuru Kawazoe, Gwénolé Lecorve, Makoto Sugita  Type  Book, Chapter in Book, Conference Proceeding  Abstract  This paper compares the XL algorithm with known Gröbner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Gröbner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Gröbner basis algorithm which can be represented as a redundant variant of a Gröbner basis algorithm F 4. Then we compare these algorithms on semiregular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields F 2 and with q≫ n. We show that the size of the matrix constructed by XL is large compared to the ones of the F 5 algorithm. Finally, we give an experimental study between XL and the Buchberger algorithm on the cryptosystem HFE and find that the Buchberger algorithm has a better behavior. Keywords: Multivariate polynomial equations, Algebraic attacks, Solving Systems, Gröbner basis, XL algorithm, Semiregular Sequences.  Length  11 
URL 
http://dx.doi.org/10.1007/9783540305392_24 
Language  English  Series  Lecture Notes in Computer Science  Volume  3329  Pages  157167  Publisher  pringer Berlin / Heidelberg  Year  2004  Note  10.1007/9783540305392_24  Editor  Lee, Pil Joong  Translation 
No  Refereed 
Yes  Book  Advances in Cryptology  ASIACRYPT 2004 
