In some recent advanced protocols, like Zero-Knowledge Proofs (allowing a prover to convince a verifier that he knows a secret without revealing it), or Multi Party Computation, algorithms do not process bit-oriented information, but rather elements of big finite fields Z/qZ. In that regard, the only operations allowed in such algorithms are additions and multiplications in the field. These protocols therefore require cryptographic algorithms that are not optimized for usual bit-oriented platforms (desktop computers, servers, microcontrollers, RFID tags…), but rather for their short implementation in Z/qZ. These are called arithmetization-oriented cryptographic algorithms.

Since 2016, several arithmetization-oriented algorithms have been presented. Their security highly depends on the complexity of polynomial root-finding and Groebner basis algorithms, which define a special class of attacks: algebraic attacks. In 2021, the Ethereum Foundation launched a series of challenges on this new class of ciphers, aiming at better understanding the threat of algebraic attacks. We took that opportunity to perform a thorough study of univariate and multivariate polynomial solving algorithms in big fields.

In this talk, we present an overview of existing algebraic attacks and analysis, along with new theoretical and experimental results on several ciphers.