I read that we do not know if there exists an 8x8 sbox with differential uniformity = 2.
I suppose we cannot compute every possible sbox because there are $64!$ possible s-boxes. Am I right?
1
-
2$\begingroup$ This is a part of the yet unsolved Big APN Problem. Do you want me to elaborate it in an answer? $\endgroup$– holaSep 7, 2017 at 2:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
There are 256! possible 8x8 S-boxes (i.e., bijective functions from $\{0,1\}^8$ to $\{0,1\}^8$). This is an absolutely enormous number. You couldn't possibly enumerate all of them within the lifetime of the universe. So, yes, this is one reason why it is not straightforward to determine whether there exists such a S-box with differential uniformity 2.
$\begingroup$
$\endgroup$
This is intended to give some background to the general problem, to complement @forest's excellent answer.
The big APN problem is the question of existence of an APN permutation (invertible Sbox) on a finite field $\mathbb{F}_{2^n}$ (or the equivalent vectorial version on $n$ bits) with $n$ even. So you want differential uniformity of $\delta=2.$
This paper by Perrin et al addresses in detail Dillon's example (unfortunately paywalled and for $n=6$ bits only) of a positive solution to the big APN problem.
Of course one is also interested in nonlinearity against linear attacks. For $n$ odd (used in Kasumi cipher Sbox) such APN permutations exist. One might argue $n$ odd is not practical for modern ciphers.
Here is a nice recent paper with a discussion which is quite readable.
Also, don't forget that one does not need an Sbox to be a permutation, e.g., if one uses a Feistel structure. Thus, known APN functions, if posessing good nonlinearity properties as well are also of interest. Such examples are known. Here is a paper with some constructions.
