This should be pretty simple question I presume. So let's say I have an 8x8 S-Box. I can easily treat it as 8 different boolean functions for each of the 8 input bits. Is the non-linearity the lowest linearity of each boolean function? Or is there something else that needs to considered with an S-Box? If it is different how does one go about calculating the linearity then?
1
-
$\begingroup$ Did you read Matsui's paper or Hayes tutorial? $\endgroup$– kelalakaJun 13, 2022 at 14:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Not quite. The non-linearity needs to apply to any linear combination of input bits correlating with any linear combination of outputs bit. More mathematically, we'd like to know $$\max_{\alpha,\beta\in\mathbb (F_2)^8}\left|\sum_{x\in(\mathbb F_2)^8}(-1)^{\alpha\cdot x\oplus\beta\cdot S(x)}\right|.$$
If only consider the individual output bits, this only maximises over values of $\beta$ with Hamming weight 1.
We could compute the above maximum by exhausting over $\beta$ and computing the linearity of each corresponding Boolean, but it can also be efficiently computed by treating the S-box as a 16-bit Boolean function which is 1 if the input is of the form $(x,S(x))$ and 0 otherwise and then computing a Walsh-Hadamard transform on this function.
-
$\begingroup$ Hi Daniel, this was answered previously as well: crypto.stackexchange.com/questions/37838/… $\endgroup$– kodluJun 13, 2022 at 14:30