# Non-linearity of a boolean function

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?

-
As is, your question is too broad! What exactly don't you get? What did you try? What have you researched? I mean, it only took a second using a random search engine to find a truckload of papers related to the subject. One of many examples: "On the nonlinearity of boolean functions" by Institut de Mathématiques de Luminy (C.N.R.S.). As you'll notice, it's a rather broad subject with a wide spectrum of involved maths, so you would need to narrow down your question to what exactly you don't mathematically get. –  e-sushi Oct 18 '13 at 11:40
@e-sushi I've edited the question. Thanks –  Mahdi Khosravi Oct 18 '13 at 12:18
Thanks, that surely helps. [+1] –  e-sushi Oct 18 '13 at 12:20
I've retagged this question, since it's certainly not about functional-encryption. However, if anyone can think of any more specific appropriate tags, feel free to add them. –  Ilmari Karonen Oct 19 '13 at 12:38
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. –  tylo Oct 13 at 14:40

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.