@inproceedings{f267bb7ce50e496994092541c9d166c9,
title = "Flexible partial enlargement to accelerate Gr{\"o}bner basis computation over double-struck F2",
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{\"o}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{\"o}bner basis computation. The new proposed algorithm computed a Gr{\"o}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{\"o}bner bases solver.",
keywords = "Algebraic cryptanalysis, Complexity, Gr{\"o}bner basis, HFE",
author = "Johannes Buchmann and Daniel Cabarcas and Jintai Ding and Mohamed, {Mohamed Saied Emam}",
year = "2010",
doi = "10.1007/978-3-642-12678-9_5",
language = "English",
isbn = "3642126774",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "69--81",
booktitle = "Progress in Cryptology - AFRICACRYPT 2010 - Third International Conference on Cryptology in Africa, Proceedings",
note = "3rd International Conference on Cryptology in Africa, AFRICACRYPT 2010 ; Conference date: 03-05-2010 Through 06-05-2010",
}