1
$\begingroup$

I am trying to find out and learn more about Balanced boolean functions.

Wikipedia states that " a balanced boolean function is a boolean function whose output yields as many 0s as 1s over its input set", and states that an example of this is XOR.

I want to know how the same works for multi-output bit functions, where the output is a concatenation of two boolean functions essentially. Truth tables with examples for single and multi output to understand what this exactly means would be good to analyze it more.

$\endgroup$
1
$\begingroup$

As in the other answer a vectorial boolean function with $m$ coordinates $f : \{0,1\}^n\to\{0,1\}^m$ are viewed as $m$ boolean functions $f_i : \{0,1\}^n\to\{0,1\}$.

However, it is not enough to consider $f$ to be balanced when the $f_i$ are all balanced.

For example consider $m=2,$ and $f_i(x_1,x_2,x_3)=x_1\oplus x_2,$ for $i=1,2.$ The truth table for $f_i$ is $[01100110]$ in the natural order. However, the function $f(x_1,x_2)=(f_1,f_2)$ does not have a property that we would call balanced since its truth table would be $[00,11,11,00,00,11,11,00].$

A natural requirement for a balanced vectorial boolean function with $m$ output coordinates is that all $2^m$ output $m-$tuples occur equally often in its truth table.

One way to ensure this holds is to stipulate that for all nonzero vectors $(a_1,\ldots,a_m)$ in $\{0,1\}^m,$ the boolean function $\langle a,f \rangle=a_1 f_1\oplus a_2 f_2 \oplus a_m f_m$ is itself balanced.

So if we had $f_1=x_1,f_2=x_1\oplus x_2,$ in the above example our function would be balanced with truth table $[00,11,01,10,00,11,01,10]$.

Usually we require other properties in addition to being balanced, such as high algebraic immunity, correlation immunity [=resilience if balanced], high nonlinearity, etc.

There is a good survey by Claude Carlet easily discovered online entitled "vectorial boolean functions". Early papers by Nyberg gave examples of nice balanced vectorial functions. Clearly if $m=n,$ and the function is balanced, you a nice $m\times m$ S-box, since each output pattern occurs exactly once and we have a permutation.

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