3
$\begingroup$

I have studied many literature on boolean functions. The nonlinearity of a boolean function is defined as min of hamming distance of the function from all the linear functions in the set. There is also formulas for calculating nonlinerity of boolean function in terms of no of inputs (n). Now i have following two doubts

  1. Is the nonlinearity of all boolean functions in the same boolean space(say V5) is same or different for different functions ? IF different then how to calculate nonlinearity of each one seperatly ?

  2. How to calculate minimum nonlinearity of a given boolean function in a given boolean space say(V5).

$\endgroup$
  • $\begingroup$ There seem to be errors in your question, e.g. the linearity of a boolean function cannot be calculated from the number of inputs. $\endgroup$ – Elias Oct 27 '16 at 12:02
  • $\begingroup$ Basically i mean the maximum nonlinearity of the function from a given boolean function in that space. e.g all balanced boolean function having 4 input have max nonlinearity of 4 $\endgroup$ – DeoChandra Oct 27 '16 at 12:35
  • $\begingroup$ But if you are talking about a maximum over a set then what are the different sets in your first question? What would the maximum non-linearity of a single function be? $\endgroup$ – Elias Oct 27 '16 at 13:09
  • $\begingroup$ Also, what exactly is your definition of a boolean space? $\endgroup$ – Elias Oct 27 '16 at 13:09
4
$\begingroup$

You can give a boolean function by it's truth table. For example if $f(x, y, z) = x + z$ you have the following truth table:

  x   y   z   f(x, y, z) = x + z
 ----------------------
  0   0   0     0
  0   0   1     1
  0   1   0     0
  0   1   1     1
  1   0   0     1
  1   0   1     0
  1   1   0     1
  1   1   1     0

just enumerating the last columns gives you $(0, 1, 0, 1, 1, 0, 1, 0)$. This $f$ is by its definition clearly a linear function. If you want to enumerate all linear functions you can look at the Hadamard matrix and Hadamard transform.

To calculate the linearity of a boolean function $g$ as explained in this question you take the minimum Hamming distance between the output vector of $g$ and all linear functions.

So if your function would for example be $g = (1, 0, 0, 0, 1, 1, 0, 1)$ the Hamming distance to $f$ would be.

g: 1 0 0 0 1 1 0 1
f: 0 1 0 1 1 0 1 0
------------------
   1 1 0 1 0 1 1 1 => HD 6 => non-linearity at most 6

In fact if you where to try all linear functions you would find $h = (0, 0, 0, 0, 1, 1, 1, 1)$ with

g: 1 0 0 0 1 1 0 1
h: 0 0 0 0 1 1 1 1
------------------
   1 0 0 0 0 0 1 0 => HD 2

and this is the lowest value so the non-linearity of $g$ is 2.

I hope this answers your second question.

Now we can answer your first question simply by finding examples. Here are two 4-bit functions with different non-linearity:

  1. [1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
    Non-linearity here is 2. It cannot be more than 2 because the middle two bits are swapped from
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
    which is clearly linear (depends only on highest value bit). And it cannot be less than 2 because the function is non-linear and balanced.
  2. [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0] has non-linearity 4.

This, I hope answers your first questions negatively. Not all functions have the same non-linearity.

$\endgroup$
  • $\begingroup$ 1.According to your answer can we say that minimum nonlinearity of function f is 6 and minimum is 2 ? Do we need to find TT of all possible linear functions for calculating the nonlinearity by finding min distance? In 4 bit example are you finding the nonlinearity just by seeing how many bits have been swaped from vector [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]. $\endgroup$ – DeoChandra Oct 28 '16 at 4:54
  • $\begingroup$ correction in above comment maximum nonlinearity of function f is 6 and minimum is 2. $\endgroup$ – DeoChandra Oct 28 '16 at 5:11
  • $\begingroup$ No, f is linear so it's non-linearity is 0. Yes, you have to calculate the HD to all linear functions and take the minimum to get the non-linearity. $\endgroup$ – Elias Oct 28 '16 at 11:29
  • $\begingroup$ I have still a doubt about 4bit examples you have given. You are saying "Non-linearity here is obviously 2 because the middle two bits are swapped from " So my doubt is that can we find nonlinearity of [1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0] just by seeing how many bits have been swapped from the [1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0] $\endgroup$ – DeoChandra Oct 28 '16 at 11:54
  • $\begingroup$ I have edited the answer. I hope it is clearer now. No, you can not find non-linearity from swapped bits in general. But a non-linearity of 2 is already pretty small (remember you take the minimum). Since the function is balanced (which means non-linearity is even) and non-linear (so it cannot be zero). This must be the correct value. $\endgroup$ – Elias Oct 28 '16 at 13:09
1
$\begingroup$

Let $V_n$ be the vector space of dimension $n$ over the binary field $F_2$ and let $f:V_n\rightarrow F_2.$

The Walsh Hadamard transform coefficient $\hat{f}(a)$ is defined as $$\hat{f}(a)=\sum_{x \in V_n} (-1)^{f(x)+a\cdot x}=\sum_{x \in V_n} (-1)^{f(x)}(-1)^{a\cdot x}=2^n-2 d_H(f,L_a)$$ where we define the linear function $L_a(x)=a\cdot x,$ and note that $d_H(f,L_a)$ denotes the Hamming distance between the truth tables of $f$ and $L_a$. To clarify when $f(x)$ agrees with $L_a(x)$ on a specific $x$ the product in the sum is $+1,$ otherwise it is $-1.$

Clearly $f$ is linear, if and only if $\hat{f}(a)=\pm 2^n$ for some $a \in V_n.$

As the other answer to this question alludes to, for an arbitrary function, there is no easy/direct way of obtaining nonlinearity from the truth table, short of evaluating the full algebraic normal form $$f(x_1,\ldots,x_n)=a_0+a_1 x_1+\cdots+a_n x_n+ a_{12} x_1 x_2 +\cdots+a_{12\cdots n} x_1 x_2 \cdots x_n$$ for which an algorithm similar in complexity to the Walsh Hadamard transform exists, given the truth table of $f$ as the input.

However, there is an efficient randomized way of verifying that the function is nonlinear (BLR testing) just pick $x,x'\in V_n$ randomly and check if $f(x)+f(x')=f(x+x')$ from the truth table (assuming fast access to any position you like of the truth table).

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