Paper 2020/1587

On the properties of the Boolean functions associated to the differential spectrum of general APN functions and their consequences

Claude Carlet

Abstract

We initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma_F$ related to the differential spectrum of $F$ (which is known to be bent if and only if $F$ is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with bent components $v\cdot F$, $v\neq 0_n$, of $F$. We pose three related open problems. We characterize further in terms of $\gamma_F$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of $\gamma_F$ and the Walsh transform of $F$. By applying the Titsworth relation to the Walsh transform $W_{\gamma_F}$, we deduce a very simple new relation satisfied by $W_F^2$. From this latter relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, that is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of $\gamma_F$ and $F$ are related by a simple formula; this leads to a last open problem.