| 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  [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >] | |
| 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.
