MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

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

Johannes Buchmann FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany Daniel Cabarcas Department of Mathematical Sciences, University of Cincinnati Jintai Ding Department of Mathematical Sciences, University of Cincinnati, South China University of Technology Mohamed Saied Emam Mohamed FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany

TBD mathscidoc:2207.43051

AFRICACRYPT 2010, 69–81, 2010.5
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.
No keywords uploaded!
[ Download ] [ 2022-07-14 13:30:27 uploaded by dingjt ] [ 400 downloads ] [ 0 comments ] 
@inproceedings{johannes2010flexible,
  title={Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over $\mathbb{F}_2$},
  author={Johannes Buchmann, Daniel Cabarcas, Jintai Ding, and Mohamed Saied Emam Mohamed},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714133027747195628},
  booktitle={AFRICACRYPT 2010},
  pages={69–81},
  year={2010},
}
Johannes Buchmann, Daniel Cabarcas, Jintai Ding, and Mohamed Saied Emam Mohamed. Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over $\mathbb{F}_2$. 2010. In AFRICACRYPT 2010. pp.69–81. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714133027747195628.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved