Deciding EA-equivalence via invariants

Abstract

We define a family of efficiently computable invariants for (n,m)-functions under EA-equivalence, and observe that, unlike the known invariants such as the differential spectrum, algebraic degree, and extended Walsh spectrum, in the case of quadratic APN functions over \(\mathbb {F}_{2^n}\) with n even, these invariants take on many different values for functions belonging to distinct equivalence classes. We show how the values of these invariants can be used constructively to implement a test for EA-equivalence of functions from \(\mathbb {F}_{2}^{n}\) to \(\mathbb {F}_{2}^{m}\); to the best of our knowledge, this is the first algorithm for deciding EA-equivalence without resorting to testing the equivalence of associated linear codes.