# Examples of multi output bit balanced Boolean functions

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.

## 1 Answer

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.