Cryptology ePrint Archive: Report 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.

Category / Keywords: XL,RXL, multivariate cryptography, system of quadratic equations, algebraic attack

Date: received 22 Apr 2005, withdrawn 10 Jul 2005

Contact author: tangxij at mails gscas ac cn

Available format(s): (-- withdrawn --)

Note: Any comments are welcome :)

Version: 20050711:012858 (All versions of this report)

Short URL: ia.cr/2005/128

Discussion forum: Show discussion | Start new discussion