# Design criteria for AES

I hope somebody can help me understand the design criterias for AES. Therefore, I would be really thankful if somebody could explain "non-linearity" in this context.

A criteria for the s-box in AES is non-linearity, where the maximum input-output correlation amplitude must be as small as possible. Why is a look-up table non-linear?

The maximum difference propagation probability must be as small as possible. This means to get closer to a uniform distribution?

MixColumns offers linearity - because it is a function which transforms values in a deterministic way?

• I suggest a look at this – fgrieu Sep 20 '12 at 9:39

Generally speaking, a function $f()$ is linear if $f(x+y) = f(x)+f(y)$ and $f(ax) = af(x)$.
The AES S-Box, which is a specific, predefined (key-independent) lookup table, doesn't satisfy these properties. You can do a quick verfication by picking two values $x,y \in GF(2^8)$ and verifying that $S(x+y) \neq S(x)+S(y)$ (where the addition operation is done in the field $GF(2^8)$, and is thus essentially the XOR operation). But the S-Box not being fully linear is not enough. It's very bad if it's just somewhat linear, in the following sense. There are various ways to define it. One of them is the Linear Property of the S-box, $LP(S) = \max_{a,b} (Pr_x(a(S(x)) == b(x)) - \frac{1}{2})^2$ which has to be low. It measures the existence of two linear functionals $a(),b()$ which tend to agree (correlate) or disagree on the input and output of the S-box. If you were to calculate $LP(S)$ you would find that it is considerably lower than for a random lookup table ("the maximum input-output correlation amplitude must be as small as possible").
As for difference propagation, a similar property exists $DP(S) = \max_{a,b\neq0} (Pr_x(S(x)\oplus a == S(x \oplus b)))$, which measures the existence of two differences (deltas) $a,b \neq 0$ which propagate through the S-box. Again this has to be minimal, and if you were to calculate $DP(S)$ you would find it is indeed lower than for a random lookup table.
• The definition of linear given is valid in some context, but not cryptanalysis. In particular, $f(x)=x+1$ is not linear by that definition. I have seen $\exists k, \forall(x,y), f(x+y)=f(x)+f(y)+k$. – fgrieu Sep 20 '12 at 10:28