On self-equivalences of APN functions

Abstract

In this thesis we investigate the structure of what we call extended linear self-equivalences for vectorial Boolean functions. That is, $(L_1, L_2, L)$ such that $L_1 \circ F \circ L_2 + L = F$ for some vectorial Boolean function F, where $L_1$ and $L_2$ are linear permutations and L is a linear function. We implement a parallel version of an algorithm for testing EA equivalence in the programming language Rust. This allows us to compare the performance of implementations in C and Rust for similar problems and to conclude that our Rust implementation is comparable in efficiency while being significantly easier to write and maintain. Using our implementation we calculate the self-equivalences for all known quadratic APN functions up to CCZ equivalence in dimensions 6, 8 and 10. We discover functions with trivial linear self-equivalence, but with nontrivial EL self-equivalences. Based on this we formulate a search procedure for obtaining new APN functions, which exploits extended linear self-equivalences in the same way that the search of Beierle et al. exploits linear self-equivalences. From the initial test runs of our new algorithm we discover that the search allows us to start from a given APN function and find APN functions CCZ-inequivalent to it. More interestingly we observe that the search can even find non-quadratic APN functions.