On the construction of differentially 4-uniform involutions

An involution is a permutation whose compositional inverse is itself. Differentially 4-uniform involutions with high algebraic degree and high nonlinearity are important for the design of block ciphers because they possess good cryptographic properties and the same component can be used in both encryption circuit and decryption circuit. A well known differentially 4-uniform involution is the multiplicative inverse function, which is used as the S-boxes in AES and Camellia. Although many differential 4-uniform permutations have been constructed, there are only a few classes of differentially 4-uniform involutions. Recently, Charpin et al. presented an idea of constructing involutions, which is called piece by piece construction. With this method, we construct a family of differentially 4-uniform involutions with optimal algebraic degree and high nonlinearity. It is also shown with the help of computer that such involutions which are CCZ-inequivalent to the known differentially 4-uniform permutations in small number of even dimensions are constructed. Furthermore, the number of CCZ-inequivalent classes of our involutions over F2n increases exponentially when n increases.