Paper 2020/1529 Original: eprint.iacr.org/2020/1529 ↗

Bounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions

Abstract

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta$-uniform functions. We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta$-uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m< n$, and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$; we study the tightness of this latter bound; this leads to an interesting question on APN functions, to which we answer. We finally make more precise the bound on the differential uniformity which was the starting point of the paper.