Reference : Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem |
Scientific congresses, symposiums and conference proceedings : Paper published in a book | |||
Engineering, computing & technology : Computer science | |||
Computational Sciences | |||
http://hdl.handle.net/10993/28414 | |||
Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem | |
English | |
Perrin, Léo Paul [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >] | |
Udovenko, Aleksei [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >] | |
Biryukov, Alex ![]() | |
21-Jul-2016 | |
Advances in Cryptology – CRYPTO 2016 | |
Robshaw, Matthew | |
Katz, Jonathan | |
Springer Berlin Heidelberg | |
93-122 | |
Yes | |
International | |
978-3-662-53007-8 | |
Berlin | |
Germany | |
36th Annual International Cryptology Conference | |
August 14-18, 2016 | |
nternational Association for Cryptologic Research | |
Santa Barbara | |
USA CA | |
[en] Boolean functions ; Bitsliced implementation ; Feistel Network ; CCZ-equivalence ; S-Box decomposition ; Butterfly structure ; APN | |
[en] 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. | |
Fonds National de la Recherche - FnR | |
Researchers | |
http://hdl.handle.net/10993/28414 | |
10.1007/978-3-662-53008-5_4 | |
http://eprint.iacr.org/2016/539 | |
FnR ; FNR4009992 > Alex BIRYUKOV > ACRYPT > Applied Cryptography for the Internet of Things > 01/01/2013 > 30/06/2016 > 2012 |
File(s) associated to this reference | ||||||||||||||
Fulltext file(s):
| ||||||||||||||
All documents in ORBilu are protected by a user license.