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
-
CC BY