eprint.iacr.orgpaperComparative Evaluation of Open-Source Gröbner Basis Implementations for Small-Scale AES Polynomial Systems over GF(2)
This IACR ePrint paper benchmarks 20 open-source Gröbner basis implementations against the proprietary Magma system on polynomial systems derived from small-scale AES over GF(2), using Easy/Medium/Hard difficulty tiers with ten instances each. In the Hard setting, msolve and Singular's slimgb completed all runs successfully with mean runtimes of 164s and 269s and peak memory of 3693/4343 MiB respectively, versus Magma's 319s and 16853 MiB, with msolve exploiting ~13.4 CPU cores versus ~1 core for the others. The results quantify when open-source algebraic solvers are practical alternatives to Magma for algebraic cryptanalysis of block ciphers.
TL;DR Benchmarks msolve, Singular's slimgb, and 18 other open-source Gröbner basis solvers against Magma on small-scale AES polynomial systems over GF(2), finding open-source tools can match or beat Magma on runtime and memory.
Organisations named here
- small-scale AES
Technologies named here
- msolve
- Small-scale AES over GF
- Singular
- Magma
- gf
Techniques named here
- Algebraic cryptanalysis via Gröbner basis computation
- F4 algorithm
Related in other
eprint.iacr.orgpaperRerandomizable Garbling for Arithmetic Circuits
aseemshrey.inarticle