Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleFlexible partial enlargement to accelerate Gr\"obner basis computation over $mathbbF_2$.
Author(s) Johannes Buchmann, Daniel Cabarcas, Jintai Ding, Mohamed Saied Emam Mohamed
TypeBook, Chapter in Book, Conference Proceeding
AbstractRecent 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.
KeywordsAlgebraic cryptanalysis, Gröbner basis, Complexity, HFE
URL http://link.springer.com/chapter/10.1007%2F978-3-642-12678-9_5
PublisherBerlin: Springer
Translation No
Refereed No