Decomposition of Dillon’s APN permutation with efficient hardware implementation

Abstract

Modern block ciphers incorporate a vectorial Boolean function (S-box ) as their only nonlinear component. Almost Perfect Nonlinear (APN) functions exhibit optimal resistance to differential cryptanalysis and thus present ideal security properties as S-boxes. These optimal cryptographic properties have the side effect of making the function harder to represent and implement. As the number of variables of the function grows, lookup-table representations become less feasible, and so from a practical point of view, it is crucial to develop a good understanding of how cryptographically strong functions can be represented in hardware. This paper focuses on one of the most important APN functions, namely Dillon’s permutation in dimension 6. This is the only known APN permutation in an even number of variables. It is thus an ideal candidate for studying the efficiency of different representations since it combines at least two very important cryptographic properties, and since the number of variables is not large enough to make its computational investigation intractable. In this paper, we give a new description of Dillon’s permutation as a composition of two functions and compare it with its classic univariate polynomial representation. We give hardware architectures for both representations, and we report on the results obtained from their FPGA implementations. From the experimental results, the implementation of the new decomposed Dillon’s permutation presents reductions in the number of 2-input XOR gates of up to 27.3% and in the Area × Delay metrics of up to 27.4% with respect to the implementation of the corresponding univariate representation. Therefore, the new decomposed Dillon’s permutation representation is more efficient than the univariate polynomial one when reconfigurable devices are used for the hardware implementation. This indicates that by representing APN functions as a composition of simpler functions, significant reductions in the complexity of the implementation can be achieved.