Paper 2004/112

Relation between XL algorithm and Groebner Bases Algorithms

M. Sugita, 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.

Note: Appendix is added.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysisalgebraic attackXL algorithmGroebner bases algorithm
Contact author(s)
m-sugita @ ipa go jp
History
2004-05-11: received
Short URL
https://ia.cr/2004/112
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/112,
      author = {M.  Sugita and M.  Kawazoe and H.  Imai},
      title = {Relation between {XL} algorithm and Groebner Bases Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2004/112},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/112}},
      url = {https://eprint.iacr.org/2004/112}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.