Affine of Inverse Sboxes

"All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties" is what this answer claims.

Is there a proof of this statement?

I am unable to see how this is true. I tried to calculate the Walsh and autocorrelation spectrum but was unable to see how they are equal.

• Most likely an error in your programming. The statement in that answer is a mathematical fact, thats been proved. You need to give more details for an answer to be feasible as to what you're doing wrong Mar 11, 2018 at 5:06
• you can read the "design of rijndael" or the aes proposal for details which may tell you where you are making a mistake. Mar 11, 2018 at 5:07
• I am looking for the proof of the mathematical fact. I am not writing any program. Mar 11, 2018 at 5:21
• ok fair enough, will edit answer Mar 11, 2018 at 5:25

To be precise, different affine transformations following the Galois field inversion should give the same Walsh spectrum up to a $\pm$ sign, in terms of how many times each value occurs. Since an affine transformation is a linear transformation plus a constant vector addition, this is not surprising.

Don't forget linear cryptanalysis measures distance to the unbiased case (prob. 1/2) so signs of Hadamard coefficients switching between positive and negative is allowed. This is how come we can ignore the sum of the non targeted key bits modulo 2 during Linear cryptanalysis, since all they would do is switch the sign of the relevant coefficient.

Let $$L_{a,b} := \sum_{x \in V_n} (-1)^{a \cdot x \oplus b \cdot S(x)}$$

where $V_n$ is the n dimensional binary vector space. Let $A x+c$ be an affine map where the linear part $x\mapsto Ax$ is full rank and thus invertible. It is then a simple matter of algebra to prove the result: $$L_{a,b}' := \sum_{x \in V_n} (-1)^{a \cdot x \oplus b \cdot (A \cdot S(x)\oplus c)}$$ by a change of basis.

Even better, in "The Design of Rijndael" by Daemen and Rijmen, (See here, Appendix A.1 onwards, provided for personal research use only) there is a coordinate free approach using trace functions on the finite field to show this.

Similar comments apply for the correlation spectrum.

• I think I am missing something here as I was not able to figure it out by reading the appendix or by your proof. Could you explain in a bit more detail. I also wrote some sage code where I found an affine of an inverse in a galois field which was unbalanced and had zero non linearity while others gave the same properties as AES. So I think that balancedness has to be a prerequisite. Mar 14, 2018 at 11:14
• Yes, since you want a one to one map, its automatically balanced. Mar 14, 2018 at 11:25