On the Derivative Imbalance and Ambiguity of Functions.

In 2007, Carlet and Ding introduced two parameters, denoted by $Nb_{F}$ and $NB_{F}$ , quantifying respectively the balancedness of general functions $F$ between finite Abelian groups and the (global) balancedness of their derivatives $D_{a} F(x)=F(x+a)-F(x)$ , $a\in G\setminus \{0\}$ (providing an indicator of the nonlinearity of the functions). These authors studied the properties and cryptographic significance of these two measures. They provided inequalities relating the nonlinearity $\mathcal {NL}(F)$ to $NB_{F}$ for S-box and specifically obtained an upper bound on the nonlinearity that unifies Sidelnikov-Chabaud-Vaudenay’s bound and the covering radius bound. At the Workshop WCC 2009 and in its postproceedings in 2011, a further study of these parameters was made; in particular, the first parameter was applied to the functions $F+L$ , where $L$ is affine, providing more nonlinearity parameters. In 2010, motivated by the study of Costas arrays, two parameters called ambiguity and deficiency were introduced by Panario et al. for permutations over finite Abelian groups to measure the injectivity and surjectivity of the derivatives, respectively. These authors also studied some fundamental properties and cryptographic significance of these two measures. Further studies followed without comparing the second pair of parameters to the first one. In this paper, we observe that ambiguity is the same parameter as $NB_{F}$ up to additive and multiplicative constants (i.e., up to rescaling). We perform the necessary work of comparison and unification of the results on $NB_{F}$ and on ambiguity, which have been obtained in the five papers devoted to these parameters. We generalize some known results to any finite Abelian groups. More importantly, we derive many new results on these parameters. [ABSTRACT FROM AUTHOR]