Constructing Differentially 4-Uniform Permutations Over F22k via the Switching Method

Many block ciphers use permutations defined on F-22k with low differential uniformity, high nonlinearity, and high algebraic degree as their S-boxes to provide confusion. It is well known that, for a function on F-2n, the lowest differential uniformity is 2 and the functions achieving this lower bound are called almost perfect nonlinear (APN) functions. However, due to the lack of knowledge on APN permutations on F-22k, differentially 4-uniform permutations are usually chosen as S-boxes. For example, the currently endorsed Advanced Encryption Standard chooses one such function, the multiplicative inverse function, as its S-box. By a recent survey on differentially 4-uniform permutations over F-22k, there are only five known infinite families of such functions, and most of them have small algebraic degrees. In this paper, we apply the powerful switching method to discover many CCZ-inequivalent infinite families of such functions on F-22k with optimal algebraic degree, where is an arbitrary positive integer. This greatly expands the list of differentially 4-uniform permutations and hence provide more choices for the S-boxes. Furthermore, lower bounds for the nonlinearity of the functions obtained in this paper are presented and they imply that some infinite families have high nonlinearity.