Testing generalized affine equivalence and applications to the classification of GAPN functions

Abstract For functions over the finite field $$\mathbb {F}_{p^n}$$ , we study a generalization of affine equivalence. Two functions of algebraic degree d are equivalent if, when ignoring monomials of algebraic degree $$d-1$$ or less, they coincide with two affine equivalent functions. This equivalence appears naturally for functions defined by the properties of their derivatives of order $$d-1$$ . In order to test this equivalence, as usual, invariants can be used as a first approach. We describe several such invariants, based on the kernel/image of the derivatives of order $$d-1$$ and on the set of vectors orthogonal to those images (similar to the orthoderivatives used as invariants for quadratic APN functions). We also define a canonical form with respect to left composition with linear transformations, which decreases the computational effort of testing for equivalence. We then apply these techniques and computer search to classify all GAPN (generalized APN) functions of algebraic degree 3 over $$\mathbb {F}_{3^3}$$ . We determined that there are exactly 31 equivalence classes; for each class we list, firstly, a representative in multivariate algebraic normal form which is in canonical form with respect to left composition with linear transformations; secondly, we also list a representative with a shortest univariate representation. Moreover, our computations show that all of the GAPN functions of algebraic degree 3 over $$\mathbb {F}_{3^3}$$ have optimal second-order differential uniformity. While this is not always the case for other values of p and n , we show that the GAPN functions of algebraic degree p over $$\mathbb {F}_{p^n}$$ of the form $$x^{p-1+p^{\ell }}$$ with $$\gcd (\ell ,n)=1$$ do have optimal order- $$(p-1)$$ differential uniformity.