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-known characterization of APN functions by the fourth moment of their Walsh transform. We study two notions which are related to such known and new characterizations: (1) one for $(n,n)$-functions, that we call componentwise APNess (CAPNess), which is a stronger version of APNness related to the characterization by the fourth moment, and has been already considered in [On almost perfect nonlinear functions; Berger, Canteaut, Charpin and Laigle-Chapuy, IEEE Transactions on Information Theory 2006]; it 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) one for $(n,m)$-function ($m=n$, resp. $m= n-1$) that we call componentwise Walsh uniformity (CWU), 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}$. Concerning the first notion, it is easily seen, and known, that any plateaued function is CAPN if and only if it is AB and that APN power permutations are CAPN. We prove that CAPN functions can exist only if $n$ is odd; this solves an open problem by Berger et al. Concerning the second notion, we show that any APN function whose component functions are partially-bent (in particular, every quadratic APN function) is CWU, but we observe also that other APN functions like Kasami functions and the inverse of one of the Gold APN permutations are CWU. To the aim of proving 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] give more insight, for APN power functions, on the relation between the cyclic-additive difference set property and the cyclic difference set property. The author is working at finalizing this way the proof for Kasami functions in odd dimension. A stronger property proved in this same paper for the particular case of plateaued functions with unbalanced components shows a relationship between the cyclic-additive difference set property and the value set of the function. This hopefully will allow completing the proof in the case of even dimension.