Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem
The existence of Almost Perfect Non linear APN permutations operating on an even number of bits has been a long standing open question until Dillon et al. who work for the NSA, provided an example on 6 bits in 2009. In this paper, we apply methods intended to reverse engineer S Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over $GF2^3$ More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are 2n bit mappings with two CCZ equivalent representations: one is a quadratic non bijective function and one is a degree $n+1$ permutation. We show that these structures always have differential uniformity at most 4 when n is odd. A particular case of this structure is actually a 3 round Feistel Network with similar differential and linear properties. These functions also share an excellent non linearity for $n=3,5,7$ Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6 bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive.
CRYPTO