For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Relation between the XL Algorithm and Grobner Basis Algorithms
Makoto SUGITA Mitsuru KAWAZOE Hideki IMAI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Cryptography
algebraic attacks, Grobner basis algorithm, F4, XL algorithm,
Full Text: PDF>>
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 F4.