IEICE Trans - Relation between the XL Algorithm and Grobner Basis Algorithms

Relation between the XL Algorithm and Grobner Basis Algorithms

Makoto SUGITA  Mitsuru KAWAZOE  Hideki IMAI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.1   pp.11-18
Publication Date: 2006/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.1.11
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Cryptography
Keyword:
algebraic attacks,  Grobner basis algorithm,  F4,  XL algorithm,

Full Text: PDF>>

Summary:
We clarify a relation between the XL algorithm and known Grobner basis algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of algebraic equations under a special condition, without calculating a whole Grobner basis. But in our result, it is shown that to solve a system of algebraic equations with a special condition under which the XL algorithm works is equivalent to calculate the reduced Grobner basis of the ideal associated with the system. Moreover we show that the XL algorithm is a Grobner basis algorithm which can be represented as a redundant variant of a known Grobner basis algorithm F₄.