International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improve the Behavior of XL Family by Reducing the Excrescent Multiply Monomials

Authors:
Xijin Tang
Yong Feng
Download:
URL: http://eprint.iacr.org/2005/128
Search ePrint
Search Google
Abstract: The XL (EXTENDED LINEARIZATION) is an equation-solving algorithm ,which is used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many algebraic cryptanalysis used today. XL produces lots excrescent multiply monomials in the solving process. The original equations multiplied by excrescent monomials are worthless for solving equations, what's more they increase the complexity of computation. In this paper the behavior of XL is analyzed, and a new version of XL called RXL to handle this problem is presented. In RXL, part of XL's excrescent multiply monomials are removed before Gaussian Elimination, so, RXL is more efficient than XL. The experimental results show that RXL need only about 75\% computation of XL. It is easy to extend our method to the existing XL's variants, and all algorithms of XL family are improved.
BibTeX
@misc{eprint-2005-12464,
  title={Improve the Behavior of XL Family by Reducing the Excrescent Multiply Monomials},
  booktitle={IACR Eprint archive},
  keywords={XL,RXL, multivariate cryptography, system of quadratic equations, algebraic attack},
  url={http://eprint.iacr.org/2005/128},
  note={ tangxij@mails.gscas.ac.cn 12975 received 22 Apr 2005, withdrawn 10 Jul 2005},
  author={Xijin Tang and Yong Feng},
  year=2005
}