deletions | additions
diff --git a/bits4.tex b/bits4.tex
index 690849d..b35bfa1 100644
--- a/bits4.tex
+++ b/bits4.tex
...
\section{Boolean Functions}
In this section, we will introduce some functions that are very important for cryptography, i.e. \emph{Boolean functions}.\\
First we consider some examples.
Let $f:(\Fb)^3 \rightarrow \Fb$ be a polynomial function such that
$f(x,y,z)=xy+yz$.
\\
Evaluating $f$ in
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 inputs of
$f$
are three is a $3$-tuple of bits and its output is only one bit, i.e., $0$ or
$1$. $1$.\\
Let us now consider another function
$g:(\Fb)^3 \rightarrow \Fb$ defined by $g(x, y, z) = x^2 y + yz$
We want to
calculate evaluate $g$ at the same points $(0, 0, 0)$ and $(1, 1, 1)$
as
before; we
obtain that
$g(0, 0, 0) = 0$ and $g(1, 1, 1) = 0$.
We can check that $f$ and $g$ have the same values in \emph{all}
points of $(\Fb)^3$
, (and we leave this computation to the reader), so
we have
$$f (x, y, z) = g(x, y, z) \, \forall (x, y, z) \in (\Fb)^3$$
Hence $f$ and $g$ are distinct as polynomials but are equal as
functions. functions, since they give the same output for each input.
\\
Since $x^2 = x \forall x \in \Fb $, then every polynomial function
from $(\Fb)^3$
to $\Fb$ can be written as a polynomial where the degree of
every variable is
at most one, for example,
$x^3 y^2 + z^{10} xy^2 = xy + zxy$.
\\
If a monomial is such that each variable appears with exponent at most one, then it is a
\emph{squarefree} monomial.
\\
In general, it is possible to prove that every function from
$(\Fb)^3$ to $\Fb$ ,
also
different from a polynomial, can be written in a polynomial form, called the
Absolute Normal Form (ANF), where every monomial is
square free. squarefree.
\begin{Definition}\label{ANF}
Let $f:(\Fb)^3 \rightarrow \Fb$ be a function.The \emph{Absolute
...
(i.e., any function
with n binary inputs and
only one binary output) can be written by
the sum of
squared free squarefree monomials
with coefficients in $\Fb$, up to degree $n$, i.e.,
$a_0+a_1x_1+...+a_n x_n+a_{n+1}x_1x_2+...+a_dx_1x_2...x_n.$
\end{Theorem}
