Paper 2017/528

Componentwise APNness, Walsh uniformity of APN functions and cyclic-additive difference sets

Claude Carlet

Abstract

In the preprint [Characterizations of the differential uniformity of vectorial functions by the Walsh transform, IACR ePrint Archive 2017/516], the author has, for each even positive $\delta$, characterized in several ways differentially $\delta$-uniform functions by equalities satisfied by their Walsh transforms. These characterizations generalize the well-know characterization of APN functions by the fourth moment of their Walsh transform. We introduce two notions which are related to these characterizations: (1) that of componentwise APN (CAPN) $(n,n)$-function, which is a stronger version of APNness related to the characterization by the fourth moment, and is defined as follows: the arithmetic mean of $W_F^4(u,v)$ when $u$ ranges over ${\Bbb F}_2^n$ and $v$ is fixed nonzero in ${\Bbb F}_2^n$ equals $2^{2n+1}$, and (2) that of componentwise Walsh uniform (CWU) $(n,m)$-function ($m=n$, resp. $m= n-1$), which is a stronger version of APNness (resp. of differential 4-uniformity) related to one of the new characterizations, and is defined as follows: the arithmetic mean of $W_F^2(u_1,v_1)W_F^2(u_2,v_2)W_F^2(u_1+u_2,v_1+v_2)$ when $u_1,u_2$ range independently over ${\Bbb F}_2^n$ and $v_1,v_2$ are fixed nonzero and distinct in ${\Bbb F}_2^m$, equals $2^{3n}$. We observe that CAPN functions can exist only if $n$ is odd, that every plateaued function is CAPN if and only if it is AB and that APN power permutations are CAPN. We show that any APN function whose component functions are partially-bent (in particular, every quadratic APN function) is CWU, but we show also that other APN functions like Kasami functions and the inverse of one of the Gold APN permutations are CWU. To prove these two more difficult results, we first show that the CWUness of APN power permutations is equivalent to a property which is similar to the difference set with Singer parameters property of the complement of $\Delta_F=\{F(x)+F(x+1)+1; x\in {\Bbb F}_{2^n}\}$, proved in the case of Kasami APN functions by Dillon and Dobbertin in [New cyclic difference sets with Singer parameters, FFA 2004]. This new property, that we call cyclic-additive difference set property, involves both operations of addition and multiplication and is more complex. We prove it in the case of the inverse of Gold function. In the case of Kasami functions, it seems difficult to find a direct proof, even by adapting the sophisticated proof by Dillon and Dobbertin of the cyclic difference set property. But the properties of plateaued APN functions proved recently by the author in [Boolean and vectorial plateaued functions, and APN functions, IEEE Transactions on Information Theory 2015] allow proving that, for APN power functions, the cyclic-additive difference set property is equivalent to the cyclic difference set property. The case $n$ odd is then solved, but not the case $n$ even since, in such case, $F$ is not a permutation. Stronger properties proved in this same paper for the particular case of plateaued functions with unbalanced components allow proving in the same time that APN Kasami functions in even dimension are CWU and that their associated set $\Delta_F$ has the cyclic-additive difference set property. This provides as a side result a simple alternative proof of the difference set property with Singer parameters of the complement of the set $\Delta_F$ related to a Kasami APN function $F$ in even dimension, since it is known that these functions are plateaued.