Details:
Title  The Complexity Analysis of the MutantXL Family  Author(s)  Johannes Buchmann, Jintai Ding, Mohamed Saied Emam Mohamed  Type  Manual  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 ̈bner basis. The analysis of MGB suggested a new upper bound for the complexity of computing Grobner bases.  Keywords  Solving Multivariate System, Complexity, MatrixBased Al gorithms, XL, MutantXL, MGB  Length  20 
URL 
http://eprint.iacr.org/2011/036 
Language  English  Year  2011  Month  January  Translation 
No  Refereed 
No  How published  Cryptology ePrint Archive, Report 2011/036 
