Cryptology ePrint Archive: Report 2004/112
Relation between XL algorithm and Groebner Bases Algorithms
M. Sugita and M. Kawazoe and H. Imai
Abstract: We clarify a relation between the XL algorithm and Groebner bases algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of equations with a special assumption without trying to calculate a whole Groebner basis. But in our result, it is shown that the XL algorithm is also a Groebner bases algorithm which can be represented as a redundant version of a Groebner bases algorithm F4 under the assumption in XL.
Category / Keywords: foundations / cryptanalysis, algebraic attack, XL algorithm, Groebner bases algorithm
Date: received 11 May 2004, last revised 11 May 2004
Contact author: m-sugita at ipa go jp
Available format(s): PDF | BibTeX Citation
Note: Appendix is added.
Version: 20040511:205910 (All versions of this report)
Short URL: ia.cr/2004/112
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]