Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to
many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic
applications. In this paper we present a strategy for computing Gröbner basis that challenges those complexity estimates.
It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements–mutants.
This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gröbner
basis computation. The new proposed algorithm computed a Gröbner basis of a degree 2 random system with 32 variables and 32
equations using 30 GB which was never done before by any known Gröbner bases solver.
Keywords Algebraic cryptanalysis - Gröbner basis - Complexity - HFE