Paper 2026/2364

Comparative Evaluation of Open-Source Gröbner Basis Implementations for Small-Scale AES Polynomial Systems over GF(2)

Abstract

The practical performance of Gröbner basis implementations depends on the polynomial systems being solved. This work evaluates 20 open-source imple- mentations with Magma as a proprietary reference on systems derived from small-scale AES over GF(2). The Easy, Medium, and Hard experiments use field equations and ten input instances each, comparing wall-clock runtime, peak memory, success rate, and CPU usage. Implementations with no successful runs are excluded from subsequent experiments. In Hard, msolve and Singular’s slimgb completed all ten runs successfully, with mean runtimes of 164 and 269 seconds and mean peak memory consumption of 3693 and 4343 MiB, respectively, com- pared with 319 seconds and 16853 MiB for Magma. During these runs, msolve used an average of 13.4 CPU cores, while slimgb and Magma used about one core each. Magma had the shortest mean runtime in Medium, whereas msolve was fastest in Easy and Hard. Changing the plaintext-ciphertext pair count affected implementations differently, and runtimes varied between instances. The results show that open-source implementations can be competitive alternatives to Magma, with their relative performance depending on the input systems.