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
Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem
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 mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Advances in Cryptology – CRYPTO 2016
Robshaw, Matthew
Katz, Jonathan
Springer Berlin Heidelberg
36th Annual International Cryptology Conference
August 14-18, 2016
nternational Association for Cryptologic Research
Santa Barbara
[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
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):

Open access
539(1).pdfAuthor postprint679.15 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.