Paper 2005/128

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

Xijin Tang and Yong Feng

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.

Note: Any comments are welcome :)

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. Unknown where it was published
Keywords
XLRXLmultivariate cryptographysystem of quadratic equationsalgebraic attack
Contact author(s)
tangxij @ mails gscas ac cn
History
2005-07-11: withdrawn
2005-05-02: received
See all versions
Short URL
https://ia.cr/2005/128
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.