3
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.