×

Comparison between XL and Gröbner basis algorithms. (English) Zbl 1094.94024

Lee, Pil Joong, Advances in cryptology – ASIACRYPT 2004. 10th international conference on the theory and application of cryptology and information security, Jeju Island, Korea, December 5–9, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23975-8/pbk). Lecture Notes in Computer Science 3329, 338-353 (2004).
Summary: 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 semi-regular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields \(\mathbb F_{2}\) and \(\mathbb F_q\) with \(q\gg 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.
For the entire collection see [Zbl 1063.94001].

MSC:

94A60 Cryptography
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation

Software:

FGb
PDFBibTeX XMLCite
Full Text: DOI