International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Relation between XL algorithm and Groebner Bases Algorithms

Authors:
M. Sugita
M. Kawazoe
H. Imai
Download:
URL: http://eprint.iacr.org/2004/112
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12084,
  title={Relation between XL algorithm and Groebner Bases Algorithms},
  booktitle={IACR Eprint archive},
  keywords={foundations / cryptanalysis, algebraic attack, XL algorithm, Groebner bases algorithm},
  url={http://eprint.iacr.org/2004/112},
  note={ m-sugita@ipa.go.jp 12549 received 11 May 2004, last revised 11 May 2004},
  author={M. Sugita and M. Kawazoe and H. Imai},
  year=2004
}