7
$\begingroup$

What's the definition of non-linearity of a boolean function? Roughly saying it is minimum number of times it equals any affine function. But I don't get it mathematically.

For example, if $f = x_1x_2$, then all the affine functions are $g_1 = 0$, $g_2 = x_1$, $g_3 = x_2$ and $g_4 = x_1+x_2$, then the non-linearity of $f$ is the minimum Hamming distance between $f$ and $g_i$'s. But what is the Hamming distance between two functions?

$\endgroup$
  • 1
    $\begingroup$ The term "Hamming distance" is actually not correct in this context, what you are looking for is the Hamming weight, and in this context it is very helpful to look at bent functions. They provide maximum non-linearity, but for actual cryptographic functions there are also other things to conside, e.g. bent functions can fail to have an output with roughly uniform distribution of 0 and 1. Anyway, that article should give some insights. $\endgroup$ – tylo Oct 13 '14 at 14:40
8
$\begingroup$

Linear functions when expressed as polynomials only have terms of degree 1 or 0. Non-linear functions have at least one term of degree 2 or higher. For example, here is a linear boolean function: $y = ax + bz + c$, where $y$ is the output bit, $x$ and $z$ are input variables, and $a$, $b$, and $c$ are constants. Notice that none of the variables are multiplied by each other -- they are only ever multiplied by constants in a linear function.

But with non-linear boolean functions, there can be terms with more than one variable in them, e.g.: $y = axz + bx + c$. The number of variables in a given term (including when a variable is multiplied by itself) determines the 'degree' of that term, so in this example there is a term of degree two in the polynomial.

Edit to add: So your question is now what is the Hamming distance? Take two strings of equal length and xor them together, then count the number of 1's in the resulting string -- the more 1's, the greater the 'distance' between the two strings. When you take the truth table of a non-linear function (truth tables can be thought of as just another binary string) and the truth table of any linear or affine function and xor them together, there will always be at least one 1 in the result, no matter which linear or affine function you are comparing the non-linear function with. The greater the 'distance' from all linear functions, the more non-linear the function.

$\endgroup$
2
$\begingroup$

Hamming distance is calculated by, the count of two functions or input bits differ.

Ex: Let $f$ and $g$ be two functions with values $f(x) = \{1,1,1,1\}$ and $g(x) = \{1,0,0,1\}$. Here second and third bits of the above two functions differ. Hence Hamming distance equals $2$.

$\endgroup$

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.