this is for holding javascript data
Michela Ceria edited bits4.tex
about 6 years ago
Commit id: ab4d36d16ee961df92a9378511b52b1ccf7faa4e
deletions | additions
diff --git a/bits4.tex b/bits4.tex
index 01f99e8..8c62586 100644
--- a/bits4.tex
+++ b/bits4.tex
...
from $(\Fb)^3$ to $\Fb$ can be written as a polynomial $h \in \Fb[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.
\begin{Definition}\label{ANF} \begin{Definition}\label{Sqfree3}
A \emph{squarefree} monomial
in $\Fb[x,y,z]$ is a monomial where each variable appears with exponent at most one.
\end{Definition}
Even more generally, it is possible to prove that \textbf{every function} from
$(\Fb)^3$ to $\Fb$ can be written in a polynomial form, called the
...
The following function, often used in cryptography, is called the \emph{majority function}:
$$f: (\Fb)^3 \rightarrow \Fb $$
$$(\bar{x},\bar{y},\bar{z})\mapsto \bar{x}\bar{y}+\bar{x}\bar{z}+\bar{y}\bar{z}.$$
This function returns value $1$ if and only if
the majority at least two among the input bits $\{\bar{x},\bar{y},\bar{z}\}$
holds hold value $1$. Obviously, it returns $0$ otherwise, i.e. if and only if
the majority at least two among the three input bits holds value $0$.
\begin{Exercise}
Verify the above statement, by evaluating $f$ at all $3$-tuples of bits.
\end{Exercise}
We need to consider $\Fb[x_1,...,x_n]$ and so we can generalize definition \ref{Sqfree3} to the following
\begin{Definition}\label{Sqfreen}
A \emph{squarefree} monomial $\mathbf{t}$ in $\Fb[x_1,...,x_n]$ is a monomial where each variable appears with exponent at most one, that is, $0 \leq \deg_{x_1}(\mathbf{t}),\deg_{x_2}(\mathbf{t}),...,\deg_{x_n}(\mathbf{t}) \leq 1$.
\end{Definition}
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$.