0
$\begingroup$

"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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – kodlu Mar 11 '18 at 5:06
  • $\begingroup$ you can read the "design of rijndael" or the aes proposal for details which may tell you where you are making a mistake. $\endgroup$ – kodlu Mar 11 '18 at 5:07
  • $\begingroup$ I am looking for the proof of the mathematical fact. I am not writing any program. $\endgroup$ – Aditya Pradeep Mar 11 '18 at 5:21
  • $\begingroup$ ok fair enough, will edit answer $\endgroup$ – kodlu Mar 11 '18 at 5:25
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aditya Pradeep Mar 14 '18 at 11:14
  • $\begingroup$ Yes, since you want a one to one map, its automatically balanced. $\endgroup$ – kodlu Mar 14 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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