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

  • $\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
    Commented Oct 6, 2014 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$ Commented Oct 6, 2014 at 20:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.