Paper 2011/036

The Complexity Analysis of the MutantXL Family

Mohamed Saied Emam Mohamed, Jintai Ding, and Johannes Buchmann


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öbner basis. The analysis of MGB suggested a new upper bound for the complexity of computing Gröbner bases.

Available format(s)
-- withdrawn --
Publication info
Published elsewhere. Unknown where it was published
Solving Multivariate SystemComplexityMatrix-Based AlgorithmsXLMutantXLMGB
Contact author(s)
mohamed @ cdc informatik tu-darmstadt de
2011-06-12: withdrawn
2011-01-21: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.