Lecture Notes in Computer Science, 2010, Volume 6055/2010, 69-81, DOI: 10.1007/978-3-642-12678-9_5

Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over \mathbbF2\mathbb{F}_2

Johannes Buchmann, Daniel Cabarcas, Jintai Ding and Mohamed Saied Emam Mohamed

View Related Documents

Abstract

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

Fulltext Preview

Image of the first page of the fulltext document