In this section, we will introduce some functions that are very important in information theory and in cryptography, the so-called Boolean functions.
First we consider some examples. We will need polynomials with three variables and bits as coefficients, that we call \(\mathbb{F}_{2}[x,y,z]\).
For a given vector of bits \(S\), for example \(S=(\bar{x},\bar{y},\bar{z})\in(\mathbb{F}_{2})^{3}\), we define the ”parity bit” as a new bit which takes the values \(1\) or \(0\) depending on the number of bits in \(S\) holding value \(1\). If this number is odd, then the parity bit takes the value \(1\), \(0\) otherwise. To compute the parity bit we can use the following polynomial function \(p\)
\begin{equation} p:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2},\quad(\bar{x},\bar{y},\bar{z})\mapsto\bar{x}+\bar{y}+\bar{z},\nonumber \\ \end{equation} \begin{equation} p\in\mathbb{F}_{2}[x,y,z],\qquad p=x+y+z.\nonumber \\ \end{equation}Verify that the function \(p(x,y,z)\) returns the parity bit.
We are interested in a function \(f\) that returns \(1\) if a vector of bits is null, \(0\) otherwise.
This is a useful Boolean function, since it recognizes whether a vector of bits is the null vector \((0,\ldots,0)\).
We now show how to obtain a polynomial representing this function. We observed in Exercise \ref{XorIsNice} that the multiplication of bits has the same truth table of the \(\mathrm{AND}\) operator. In particular we have \(1\) if each bit is \(1\), \(0\) otherwise. This is the opposite of what we want and so we can add \(1\) to have the sought-after function (see Exercise \ref{Not}). For example, if \(n=3\) the function becomes
In Exercise \ref{XorIsNice} we observed that the operator \(\mathrm{OR}\) corresponds to neither the sum in \(\mathbb{F}_{2}\) nor the multiplication in \(\mathbb{F}_{2}\). We would like to define a Boolean function
\begin{equation} o:(\mathbb{F}_{2})^{2}\rightarrow\mathbb{F}_{2},\,o\in\mathbb{F}_{2}[x,y],\,(x,y)\mapsto o(x,y),\nonumber \\ \end{equation}that corresponds to the \(\mathrm{OR}\) operator. We need the De Morgan law, which is used in logic:
\begin{equation} \mathrm{NOT}(x\,\mathrm{OR}\,y)=\mathrm{NOT}(x)\,\mathrm{AND}\,\mathrm{NOT}(y)\nonumber \\ \end{equation}From this we deduce that
\begin{equation} o(x,y)=\mathrm{NOT}(\mathrm{NOT}(x\,\mathrm{OR}\,y))=\mathrm{NOT}(\mathrm{NOT}(x)\,\mathrm{AND}\,\mathrm{NOT}(y)).\nonumber \\ \end{equation}Since the operator \(\mathrm{AND}\) corresponds to multiplication, the above formula becomes
\begin{equation} o(x,y)=\big{(}(x+1)(y+1)\big{)}+1,\nonumber \\ \end{equation}which is (after simplifications)
\begin{equation} o(x,y)=xy+x+y.\nonumber \\ \end{equation}Find the Boolean function corresponding \(x\,\mathrm{OR}\,(y\,\mathrm{OR}\,z)\).
Let \(f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\) be a polynomial function such that
\(f(x,y,z)=xy+yz\).
Evaluating \(f\) at the \(3\)-tuple \((0,0,0)\) we get \(f(0,0,0)=0+0=0\),
and evaluating
it in
\((1,1,1)\) we get \(f(1,1,1)=1\cdot 1+1\cdot 1=1+1=0\).
Note that the input of
\(f\) is a \(3\)-tuple of bits and its output is only one bit.
Let us now consider also another function
\(g:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\), \(g(x,y,z)=x^{2}y+yz\).
We evaluate \(g\) at the same \(3\)-tuples \((0,0,0)\) and \((1,1,1)\)
and we
obtain that
\(g(0,0,0)=f(0,0,0)=0\) and \(g(1,1,1)=f(1,1,1)=0\).
Indeed, you can check that \(f\) and \(g\) take the same values in all
vectors of \((\mathbb{F}_{2})^{3}\), so
that
Hence, \(f\) and \(g\) are distinct as polynomials in \(\mathbb{F}_{2}[x,y,z]\), but they are equal as Boolean functions, since given an input, they return the same output!
The unexpected behaviour of the above functions \(f\) and \(g\) comes from the fact that \(u^{2}=u\) for any \(u\in\mathbb{F}_{2}\). Therefore, every polynomial function from \((\mathbb{F}_{2})^{3}\) to \(\mathbb{F}_{2}\) can be written as a polynomial \(h\in\mathbb{F}_{2}[x,y,z]\) where \(0\leq\deg_{x}(h),\deg_{y}(h),\deg_{z}(h)\leq 1\), for example, \(x^{3}y^{2}+z^{10}xy^{2}=xy+zxy\), as a Boolean function.
A squarefree monomial in \(\mathbb{F}_{2}[x,y,z]\) is a monomial where each variable appears with exponent at most one.
Even more generally, it is possible to prove that every function from \((\mathbb{F}_{2})^{3}\) to \(\mathbb{F}_{2}\) can be written in a polynomial form, called the Absolute Normal Form (ANF), where every monomial is squarefree.
Let \(f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\). The Absolute Normal Form of \(f\) is
\begin{equation} f(x,y,z)=axyz+bxy+cxz+dzy+\alpha x+\beta y+\gamma z+\delta,\nonumber \\ \end{equation}where \(a,b,c,d,\alpha,\beta,\gamma,\delta\) are in \(\mathbb{F}_{2}\).
In the ANF of any \(f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\) there are at most:
one monomial of degree 3 \(\rightarrow xyz;\)
three monomials of degree 2 \(\rightarrow xy,\quad xz,\quad zy;\)
three monomials of degree 1 \(\rightarrow x,\quad y,\quad z;\)
one monomial of degree 0 \(\rightarrow 1;\)
where a monomial appears if and only if its corresponding coefficient is nonzero.
We show now that every function from \((\mathbb{F}_{2})^{3}\) to \(\mathbb{F}_{2}\) can be written in ANF.
Consider the set \(B_{3}=\{f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\}\) of all functions from \((\mathbb{F}_{2})^{3}\) to \((\mathbb{F}_{2})\).
Since the functions from \((\mathbb{F}_{2})^{3}\) to \((\mathbb{F}_{2})\) with ANF are a special kind of functions from \((\mathbb{F}_{2})^{3}\) to \((\mathbb{F}_{2})\), then we have the following set inclusion
By Definition \ref{ANF}, in the ANF of a Boolean function \(f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\) there are \(8\) coefficients \(a,b,c,d,\alpha,\beta,\gamma,\delta\in\mathbb{F}_{2}\). Each of them may hold value \(0\) or \(1\), depending on the function \(f\), so we have two choices for each coefficient. Thus, we have at most \(2^{8}\) functions in \(\{f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\textrm{ with ANF}\}\). The number of functions in \(B_{3}\) with ANF may be less than \(2^{8}\) only in the case when two different choices on the coefficients of the ANF lead to the same function. This case is impossible since
if \(f,g\in\mathbb{F}_{2}[x,y,z]\) are in ANF and \(f\neq g\) in \(\mathbb{F}_{2}[x,y,z]\), then \(f\neq g\) in \(B_{3}\), i.e. there is at least a \(3\)-tuple of bits \((u,v,w)\in(\mathbb{F}_{2})^{3}\) such that \(f(u,v,w)\neq g(u,v,w)\)
(we do not prove this last claim, leaving it as a useful exercise to the reader).
Now, pointing out that the size of \(B_{3}\) is \(|B_{3}|=|(\mathbb{F}_{2})^{3}|=2^{8}\), so there are as many functions in \(B_{3}\) as the number of
possible ANF’s, we get that
hence every function from \((\mathbb{F}_{2})^{3}\) to \(\mathbb{F}_{2}\) can be written in Absolute Normal Form.
Consider the function \(f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\)
defined by
\(f(0,0,0)=0,\,f(0,0,1)=0,\,f(0,1,0)=1,\,f(0,1,1)=1,\,\)
\(f(1,0,0)=1,\,f(1,0,1)=1,\,f(1,1,0)=0,\,f(1,1,1)=1\,.\)
We want to derive the ANF of \(f\). We know that it is something like
for some \(a,b,c,d,\alpha,\beta,\gamma,\delta\in\mathbb{F}_{2}\).
By evaluating the ANF at \((0,0,0)\) we see that \(f(0,0,0)=\delta\). By definition of \(f\), \(f(0,0,0)=0\), so we have identified \(\delta\) as \(\delta=0\).
By evaluating the ANF at \((1,0,0)\) we see that \(f(1,0,0)=\alpha+\delta=\alpha\). By definition of \(f\), \(f(1,0,0)=1\), so we have identified \(\alpha\) as \(\alpha=1\).
Similarly we deduce \(\beta=1\) and \(\gamma=0\).
By evaluating the ANF at \((1,1,0)\) we see that \(f(1,1,0)=b+\alpha+\beta+\delta=b\). By definition of \(f\), \(f(1,1,0)=0\), so we have identified \(b\) as \(b=0\).
Similarly \(c=0\) and \(d=0\).
Finally, by evaluating the ANF at \((1,1,1)\) we see that \(a=1\). The final result is \(f=xyz+x+y\).
Determine the ANF of the function defined by
\(f(0,0,0)=0,\,f(0,0,1)=0,\,f(0,1,0)=1,\,f(0,1,1)=1,\,\)
\(f(1,0,0)=1,\,f(1,0,1)=1,\,f(1,1,0)=1,\,f(1,1,1)=1\,.\)
The following function, often used in cryptography, is called the majority function:
\begin{equation} f:(\mathbb{F}_{2})^{3}\rightarrow\mathbb{F}_{2}\nonumber \\ \end{equation} \begin{equation} (\bar{x},\bar{y},\bar{z})\mapsto\bar{x}\bar{y}+\bar{x}\bar{z}+\bar{y}\bar{z}.\nonumber \\ \end{equation}This function returns value \(1\) if and only if at least two among the input bits \(\{\bar{x},\bar{y},\bar{z}\}\) hold value \(1\). Obviously, it returns \(0\) otherwise, i.e. if and only if at least two among the three input bits holds value \(0\).
Verify the above statement, by evaluating \(f\) at all \(3\)-tuples of bits.
Until now we have only given results and examples where a function has at most \(3\) bits in input.
We would like to consider the most general case, where the number of bits in input is an arbitrary integer \(n\geq 1\).
To do that, we need to consider \(\mathbb{F}_{2}[x_{1},...,x_{n}]\) and so we can generalize definition \ref{Sqfree3} to the following
A squarefree monomial \(\mathbf{t}\) in \(\mathbb{F}_{2}[x_{1},...,x_{n}]\) is a monomial where each variable appears with exponent at most one, that is,
\begin{equation} 0\leq\deg_{x_{1}}(\mathbf{t}),\deg_{x_{2}}(\mathbf{t}),...,\deg_{x_{n}}(\mathbf{t})\leq 1.\nonumber \\ \end{equation}We can now conclude this section with the most general formulation of the Absolute Normal Form Theorem.
Let \(n\in\mathbb{N}\). Any Boolean function
\begin{equation} f:(\mathbb{F}_{2})^{n}\rightarrow(\mathbb{F}_{2})\nonumber \\ \end{equation}can be written as a polynomial in \(\mathbb{F}_{2}[x_{1},..,x_{n}]\). More precisely, \(f\) can be written as the sum of some squarefree monomials of degree from \(0\) to \(n\), i.e.
\begin{equation} f=a_{0}+a_{1}x_{1}+...+a_{n}x_{n}+a_{1,2}x_{1}x_{2}+...a_{n-1,n}x_{n-1}x_{n}+...+a_{1,2,...,n}x_{1}x_{2}\cdots x_{n}\,,\nonumber \\ \end{equation}where \(a_{0},...,a_{1,2,...,n}\in\mathbb{F}_{2}.\)
Consider the function of Example \ref{Prodotto1}, returning \(1\) if a vector of bits is \(1\) and \(0\) otherwise. We can see that if we consider, for example, vectors of \(4\) bits, it can be represented as \(f=x_{1}x_{2}x_{3}x_{4}+1.\)