Cryptology ePrint Archive: Report 2011/036

The Complexity Analysis of the MutantXL Family

Mohamed Saied Emam Mohamed and Jintai Ding and Johannes Buchmann

Abstract: Algebraic attacks are based on the problem of solving systems of multivariate polynomial equations. The complexity of algorithms for solving this problem is essentially affected by the method of enlarging these multivariate systems. The MutantXL algorithm was presented as an efficient algorithm for solving multivariate systems. In this paper, we study the complexity of the MutantXL algorithm and give an upper bound to the number of mutants necessary for terminating the computations of the algorithm. At the ePrint archive, E. Thomae and C. Wolf recently published a new paper and presented two formulas for an upper bound on the number of linearly independent equations generated by MutantXL. We have noticed that these two formulas are not accurate. The first one leads to, indeed, a large upper bound. However, the second one does not take into account a lot of linearly independent computations. We indicate the errors in these formulas and propose new ones. Our formulas based on a theoretical evaluation of the maximum number of linearly independent equations produced by MutantXL. We have verified the new formulas with a large number of experiments on some HFE and random generated systems. Furthermore, we study the complexity of the MGB algorithm for computing Gr\"obner basis. The analysis of MGB suggested a new upper bound for the complexity of computing Gr\"obner bases.

Category / Keywords: Solving Multivariate System, Complexity, Matrix-Based Algorithms, XL, MutantXL, MGB

Date: received 20 Jan 2011, last revised 21 Jan 2011, withdrawn 12 Jun 2011

Contact author: mohamed at cdc informatik tu-darmstadt de

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

Version: 20110612:091857 (All versions of this report)

Short URL: ia.cr/2011/036

Discussion forum: Show discussion | Start new discussion