3
$\begingroup$

Page 15 of the Keccak reference (PDF) explains that the $Chi$ step mapping of the Keccak-f permutation in Keccak is defined to be “nonlinear mapping”. Without this, the complete permutation would be linear.

What does ”nonlinear” mean? The paper says that $Chi$ has algebraic degree of 2, so it is not a linear function. But now I have to explain why $Chi$ has exactly algebraic degree 2. I found this question Non-linearity of a boolean function which helped me a little bit. But I am still not sure if understand this correct:

A linear boolean function $y = ax + bz + c$ is a linear function with $y$ as output bit, $x$ and $z$ as input variable and $a$, $b$ and $c$ are constants. The variables are only multiplicated by the constants (I guess the addition and multiplication of a boolean function are defined in $GF(2)$ isn't it?)

So, a non linear boolean function is something like $y = axz + bx + c$. $x$ and $z$ are variables and the term $axz$ contains two variables, which describes the degree of $2$ in this example.

Now, the $Chi$ step mapping function is described formal as:

$a[x] <- a[x] + (a[x+1] + 1)*a[x+2]$

If we say that a[x], a[x+1] and a[x+2] is the input variables for a function like this:

$f(x, y, z) = x + (y+1)z$

we have a a degree of two in the term $(y+1)z$.

$\endgroup$
  • $\begingroup$ It seems, you have your answer already. If any summand of the function formula contains a term with higher degree than 1, it's called nonlinear. Another good reference for this is the wiki page about degree of a polynomial $\endgroup$ – tylo Oct 6 '14 at 11:29
  • 1
    $\begingroup$ After your edit, it seems that we only can say "yes" or "no" (and I would say "yes"). Maybe you could move the answering part (after the sentence "I'm not sure if I understand this correct") into an actual answer? $\endgroup$ – Paŭlo Ebermann Oct 6 '14 at 20:22

Your Answer

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

Browse other questions tagged or ask your own question.