Name
Title | ||
|---|---|---|
Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version). |
Abstract | ||
|---|---|---|
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). 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. |
Year | Venue | Field |
|---|---|---|
2016 | IACR Cryptology ePrint Archive | Differential uniformity,Discrete mathematics,Combinatorics,Permutation,Quadratic equation,Cryptanalysis,Cryptographic primitive,Parity (mathematics),Mathematics,Cube |
DocType | Volume | Citations |
Journal | 2016 | 0 |
PageRank | References | Authors |
0.34 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Léo Perrin | 1 | 54 | 9.85 |
| Aleksei Udovenko | 2 | 2 | 2.56 |
| Alex Biryukov | 3 | 2385 | 198.94 |