Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions (Q2430706)

The security of block ciphers relies mainly on the resistance of their S-boxes against common attacks such as linear or differential attacks. The S-boxes are Boolean maps defined on the hypercubes. A bent function is a Boolean map with greatest possible nonlinearity value; they exist for even dimension and are characterized by the coefficients of their Walsh transforms. The almost bent (AB) maps are defined for all dimensions and similar properties of their Walsh transforms. The perfect nonlinear (PN) maps are those whose derivatives are balanced and the almost PN (APN) are those maps whose derivatives are 2-to-1. Differentially \(r\)-uniform maps are those \(f\) such that the equation \(D_af=b\) has at most \(r\) solutions \(x\) for any \(a,b\). APN maps are optimally resistant against differential attacks and AB maps against linear and differential attacks. Thus it is quite important to look for efficient construction methods for APN and differentially \(r\)-uniform maps. In the current paper the author introduces some new procedures to obtain APN and differentially \(4\)-uniform maps and he shows that its methods subsume already known construction methods. In the first part of the paper the author analyzes three nonlinearity parameters quantifying the unbalancedness of vectorial Boolean maps and he shows a bound on the nonlinearity of a map in terms of these parameters. In his analysis, the author considers the parameter values as random variables varying on certain map classes and he characterizes expectation and variances of these random variables. The author is one of the leading experts in the field, the paper is self-contained and very motivating, and thus its reading is ``a must'' for any active researcher in the area.