Exploring the Set of APN Functions in Practice

Functions that have optimal resistance to differential attacks are called Almost Perfect Nonlinear (APN). While defining APN functions is straightforward, discovering new ones with specific properties remains a challenging task. For example, it is still unknown whether an 8-bit APN bijection exists. The only known APN bijection in even dimension is the Dillon permutation in dimension 6 which was found exploring the CCZ-equivalence class of a known quadratic APN function - the Kim mapping. However, few techniques exist that allow one to move beyond the CCZ-class of known functions. One such method, switching neighbours, was successfully used by Edel and Pott to construct a 6-bit APN function that is not CCZ-equivalent to any quadratic one. To this day, the functions in the CCZ-class of this function are the only known functions in dimension 6 that are not equivalent to a quadratic one. Recently, Beierle et al. computed more than 3.8 millions CCZ-inequivalent quadratic functions in dimension 8. It rises the following question: with such amount of quadratic functions as a starting point, is it possible to replicate the successes of Dillon or Edel and Pott in dimension 8 ?

In this presentation, we investigate known structures in the set of APN functions by establishing new results about the structure of the CCZ-equivalence class of APN functions, in particular quadratic, and new results about the structure of the set of switching neighbours. These advances allow us to build a database containing exactly one representative of each extended-affine class of APN function over 6 bits and 7-bits. Our theoretical and algorithmic improvements regarding switching neighbors make it possible to efficiently compute all switching neighbours for 6-bit and 7-bit functions, though no new APN functions were identified in this process. Nonetheless, these techniques allowed us to exhaustively compute all switching neighbors of the 3.8 million 8-bit quadratic functions in less than a day of computations, among which we report new functions. The implementations used for these computations are publicly available in the sboxU library.