|Title||The Complexity Analysis of the MutantXL Family|
|Author(s)|| Johannes Buchmann, Jintai Ding, Mohamed Saied Emam Mohamed|
|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, Matrix-Based Al- gorithms, XL, MutantXL, MGB|
|How published||Cryptology ePrint Archive, Report 2011/036|