Paper 2017/516
Characterizations of the differential uniformity of vectorial functions by the Walsh transform
Claude Carlet
Abstract
For every positive integers $n$, $m$ and every even positive integer $\delta$, we derive inequalities satisfied by the Walsh transforms of all vectorial $(n,m)$functions and prove that the case of equality characterizes differential $\delta$uniformity. This provides a generalization to all differentially $\delta$uniform functions of the characterization of APN $(n,n)$functions due to Chabaud and Vaudenay, by means of the fourth moment of the Walsh transform. Such generalization has been missing since the introduction of the notion of differential uniformity by Nyberg in 1994 and since ChabaudVaudenay's result the same year.\\ For each even $\delta\geq 2$, we find several such characterizations. In particular, when $\delta=2$ and $\delta=4$, we have that, for any $(n,n)$function (resp. any $(n,n1)$function), 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 nonzero and distinct and range independently over ${\Bbb F}_2^m$, is at least $2^{3n}$, and that $F$ is APN (resp. is differentially 4uniform) if and only if this arithmetic mean equals $2^{3n}$ (which is the value we would get with a bent function if such function could exist). These inequalities give more knowledge on the Walsh spectrum of $(n,m)$functions. We deduce in particular a property of the Walsh support of highly nonlinear functions. We also consider the completely open question of knowing if the nonlinearity of APN functions is necessarily nonweak (as it is the case for known APN functions); we prove new lower bounds which cover all power APN functions (and hence a large part of known APN functions), which explain why their nonlinearities are rather good, and we discuss the question of the nonlinearity of APN quadratic functions (since almost all other known APN functions are quadratic).
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 claude carlet @ gmail com
 History
 20170605: revised
 20170605: received
 See all versions
 Short URL
 https://ia.cr/2017/516
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/516, author = {Claude Carlet}, title = {Characterizations of the differential uniformity of vectorial functions by the Walsh transform}, howpublished = {Cryptology ePrint Archive, Paper 2017/516}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/516}}, url = {https://eprint.iacr.org/2017/516} }