Paper 2024/693

A Note on Gröbner Bases for Anemoi

Abstract

This paper focuses on algebraic attacks on the $\mathsf{Anemoi}$ family of arithmetization-oriented permutations [Crypto '23]. We consider a slight variation of the naive modeling of the $\mathsf{CICO}$ problem associated to the primitive, for which we can very easily obtain a Gröbner basis and prove the degree of the associated ideal. For inputs in ${\mathbb{F}}_q^2$ when $q$ is an odd prime, we recover the same degree as conjectured for alternative polynomial systems used in other recent works [eprint/2024/250,eprint/2024/347]. Our approach can also be adapted to other settings which have not been studied there, i.e., even characteristic fields and inputs in ${\mathbb{F}}_q^{2\ell }$ for $\ell >1$. Finally, we analyze the construction of the multiplication matrices associated to our Gröbner basis, showing that it can be achieved in a more efficient way than in the generic case.