Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleComparison Between XL and Gröbner Basis Algorithms
Author(s) Jean-Charles Faugère, Imai Hideki, Mitsuru Kawazoe, Gwénolé Lecorve, Makoto Sugita
TypeBook, Chapter in Book, Conference Proceeding
AbstractThis 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 semi-regular 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, Semi-regular Sequences.
URL http://dx.doi.org/10.1007/978-3-540-30539-2_24
SeriesLecture Notes in Computer Science
Publisherpringer Berlin / Heidelberg
EditorLee, Pil Joong
Translation No
Refereed Yes
BookAdvances in Cryptology - ASIACRYPT 2004