# Non-Linearity of an S-Box [duplicate]

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?

• Did you read Matsui's paper or Hayes tutorial? Jun 13 at 14:21

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.