On a generalisation of Dillon’s APN permutation

International audienceNonlinear functions, also called S-Boxes, are building blocks for symmetric cryptography primitives. The robustness of S-Boxes is measured using properties of Boolean functions, such as differential uniformity and non-linearity. In particular, the lower the differential uniformity, the better the resistance to differential attacks. Functions which reach the best differential uniformity, which is 2, are called Almost Perfect Nonlinear (APN). In 2009, Dillon et al. exhibited an APN permutation on six variables. This is however the only known APN permutation on an even number of variables. In 2016, Perrin et al. introduced the butterfly structure on (4k + 2) variables, which defines a family of permutations with differential uniformity of at most 4, and includes the Dillon APN permutation when k = 1 (i.e. for 6 variables). It remained to find their non-linearity and whether APN butterflies exist on more than 6 variables. In this work, we generalise butterflies by looking at involutions H R on (4k + 2) variables defined by H R (x, y) = R R −1 y (x) (y), R −1 y (x) with R : F 4k+2 2 → F 2k+1 2 such that x → R y (x) = R(x, y) is a permutation. When the algebraic degree of R (i.e. the maximal degree of the algebraic normal forms of its coordinates) is at most 3, this family includes the Dillon permutation and all permutations defined by Perrin et al. Moreover, we can use properties of degree 3 Boolean functions to study the properties of our construction and solve the two open problems from Perrin et al. We prove that all generalised butterflies have the best known non-linearity. Sadly, we also prove that the Dillon permutation is, up to affine equivalence, the only APN permutation in this family: other functions have differential uniformity 4. Anyhow, these new permutations still reach an excellent robustness and have an easy structure which allows for a lightweight implementation