Paper 2016/539

Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version)

Léo Perrin, Aleksei Udovenko, and Alex Biryukov


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 $GF(2^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.

Note: Added a proof of linear-equivalence of the monomial x^5 and the closed butterfly with e=5. Also added a few notes about the cube and kim functions. Added citation for [22].

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2016
Boolean functionsAPNButterfly structureS-Box decompositionCCZ-equivalenceFeistel NetworkBitsliced implementation
Contact author(s)
leo perrin @ inria fr
2021-05-31: last of 2 revisions
2016-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Léo Perrin and Aleksei Udovenko and Alex Biryukov},
      title = {Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/539},
      year = {2016},
      doi = {10.1007/978-3-662-53008-5_4},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.