Normality of Vectorial Boolean Functions

The most important building blocks of symmetric cryptographic primitives such as the DES or the AES, are vectorial Boolean functions, also called S-boxes. In this paper, we extend the definition of normality for Boolean functions into several new affine invariant properties for vectorial Boolean functions. We compute the probability of occurrence of these properties and present practical algorithms for each of these new properties. We find a new structural property for the AES S-box, which also holds for a large class of permutation functions when the dimension n is even. Moreover, we prove a relation with the propagation characteristics of a vectorial function and extend the scope of non-APN functions for n even.