Computational investigation of 0-APN monomials

Abstract

This thesis is dedicated to exploring methods for deciding whether a power function $F(x) = x^d$ is 0-APN. Any APN function is 0-APN, and so 0-APN-ness is a necessary condition for APN-ness. APN functions are cryptographically optimal, and are thus an object of significant interest. Deciding whether a given power function is 0-APN, or APN, is a very difficult computational problem in dimensions greater than e.g. 30. Methods which allow this to be resolved more efficiently are thus instrumental to resolving open problems such as Dobbertin's conjecture. Dobbertin's conjecture states that any APN power function must be equivalent to a representative from one of the six known infinite families. This has been verified for all dimensions up to 34, and up to 42 for even dimensions. There have, however, been no further developments, and so Dobbertin's conjecture remains one of the oldest and most well-known open problems in the area. In this work, we investigate some methods for efficiently testing 0-APN-ness. A 0-APN function can be characterized as one that does not vanish on any 2-dimensional linear subspace. We determine the minimum number of linear subspaces that have to be considered in order to check whether a power function is 0-APN. We characterize the elements of this minimal set of linear subspaces, and formulate and implement efficient procedures for generating it. We computationally test the efficiency of this method for dimension 35, and conclude that it can be used to decide 0-APN-ness much faster than by conventional methods, although a dedicated effort would be needed to exploit this further due to the huge number of exponents that need to be checked in high dimensions such as 35. Based on our computational results, we observe that most of the cubic power functions are 0-APN. We generalize this observation into a ``doubly infinite'' family of 0-APN functions, i.e. a construction giving infinitely many exponents, each of which is 0-APN over infinitely many dimensions. We also present some computational results on the differential uniformity of these exponents, and observe that the Gold and Inverse power functions can be expressed using the doubly infinite family.