[Resource Topic] 2020/1529: Bounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions

Welcome to the resource topic for 2020/1529

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

Authors: Claude Carlet

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.

ePrint: https://eprint.iacr.org/2020/1529

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .