\chapter{Introduction}

The Vector Boolean Function Library (VBF) is a collection of C++ classes designed for analyzing Vector Boolean Functions (functions that map a Boolean vector to another Boolean vector) from a cryptographic perspective. This implementation uses the NTL library from Victor Shoup, modifying some of the general purpose modules of this library (to make it better suited to cryptography), and adding new modules that complement the existing ones. The class representing a Vector Boolean Function can be initialized by several data structures such as Truth Table, Trace representation, Algebraic Normal Form (ANF) among others. The most relevant cryptographic criteria for both block and stream ciphers can be evaluated with VBF. It allows to obtain some interesting cryptologic characterizing features such as linear structures, frequency distribution of the absolute values of the Walsh Spectrum or Autocorrelation Spectrum, among others. In addition, operations such as equality checking, composition, inversion, sum, direct sum, concatenation, bricklayering (parallel application of Vector Boolean Functions as employed in Rijndael cipher), and adding coordinate functions of two Vector Boolean Functions can be executed.

\section{Functions available in VBF}\label{sec:Functions}

The library covers a wide range of topics for analyzing cryptographic properties of Vector Boolean Functions. Methods are available for the following areas:

\begin{itemize}
\item Vector Boolean Function representations and characterizations
\item Cryptographic criteria calculation
\item Constructions and operations over Vector Boolean functions
\end{itemize}

The use of these methods is described in this manual. Each chapter provides detailed definitions of the methods, followed by example programs.

\section{Conventions used in this manual}\label{sec:Conventions}

This manual contains many examples which can be typed at the keyboard. A command entered at the terminal is shown like this,

\begin{verbatim}
$ command
\end{verbatim}

The first character on the line is the terminal prompt, and should not be typed. The dollar sign $\$$ is used as the standard prompt in this manual, although some systems may use a different character.
The examples assume the use of the GNU operating system. There may be minor differences in the output on other systems. The commands for setting environment variables use the Bourne shell syntax of the standard GNU shell (bash).

\section{Software implementation}\label{sec:SW_implementation}

The package included consists of: 

\begin{enumerate}
\item Derived classes inherited from NTL base classes which add new functions on top of them:

\begin{equation}
\begin{array}{ll}
&pol.h, vbf\_GF2EX.h, vbf\_GF2X.h, vbf\_ZZ.h, vbf\_mat\_GF2.h, \\
& vbf\_mat\_RR.h, vbf\_mat\_ZZ.h, vbf\_tools.h, vbf\_vec\_GF2.h,\\ 
& vbf\_vec\_GF2E.h,  vbf\_vec\_RR.h, vbf\_vec\_ZZ.h, vec\_pol.h
\end{array}
\end{equation}

\item Main class (VBF.h) with the functions, 

\item A makefile to ease the compilation of example (Makefile),

\item A set of files associated with the decimal representation of KASUMI \cite{KASUMI:05} S-boxes (S7.dec and S9.dec).
\end{enumerate}

The Output files can be found within "KASUMI Analysis" in the "Examples" menu at the Web site \url{http://vbflibrary.tk}.

\section{System requirements}\label{sec:System_requirements}

The VBF library can be easily installed in a matter of minutes on just about
any platform, including virtually any 32- or 64-bit machine running any flavor
of Unix, as well as PCs running Windows, and Macintoshes. VBF achieves this
portability by avoiding esoteric C++ features, and by avoiding assembly code;
it should therefore remain usable for years to come with little or no
maintenance, even as processors and operating systems continue to change and
evolve.

\section{Installation}\label{sec:Installation}

We are going to illustrate the installation of the package in an Unix or Unix-like platforms (including Linux distributions). 

\begin{description}
\item[1. Download the last version of the library] from \url{https://github.com/jacubero/VBF/tree/master/src} and place it in the working directory. You should see the example program, input files and the *.h files.

\item[2. Obtain NTL library source code]. To obtain the source code and documentation for NTL, download ntl-xxx.tar.gz from \url{http://www.shoup.net/ntl/download.html}, placing it in a different directory.

\item[3. Run the configuration script]. Working in the directory where you placed the NTL library, do the following (here, "xxx" denotes the desired version number of NTL; any version of NTL can be employed):

\begin{verbatim}
$ cd ntl-xxx/src
$ ./configure
\end{verbatim}

The execution of {\em configure\/} generates the file "makefile" and the file "../include/NTL/config.h", based upon the values assigned to the variables on the command line. In the example above no arguments were employed. The most important variables are: "CC" for choosing the C compiler,
"CXX" for choosing the C++ compiler, "PREFIX" for choosing the directory in which to install NTL library components.

\item[4. Build NTL]:
\begin{verbatim}
$ make
$ make check
$ make install
\end{verbatim}

The {\em make\/} execution in the directory {\em src\/} compiles all the source files and creates a library "ntl.a" in the same directory. Some testing programs are run by means of the command {\em make check\/}. Lastly, {\em make install\/} performs among other actions the copy of the library file "ntl.a" into "/usr/local/lib/libntl.a" by default. It is not necessary to execute "make check" in each NTL building as it takes a long time. In order to execute "make install", it is necessary to have privileged user permissions as some directories creation, file deletion, changes of file attributes, and copies of files are done.

\end{description}

Do not forget to use an account with appropriate permissions: "root" for instance.

\section{Preliminaries}

The mathematical theory of Vector Boolean Functions starts with the formal
definition of vector spaces whose elements (vectors) have binary elements.
Let $< \gf{GF(2)}, +, \cdot >$ be the finite field of order $2$, where
$\gf{GF(2)} = \bbbz_2 = \{0,1\}$, '$+$' the 'integer addition modulo $2$' and
'$\cdot$' the 'integer multiplication modulo $2$'. $\gf{V_n}$ is the vector
space of $n$-tuples of elements from $\gf{GF(2)}$. The \textsl{direct sum} of
$\vec{x} \in \gf{V_{n_1}}$ and $\vec{y} \in \gf{V_{n_2}}$ is defined as
$\vec{x} \oplus \vec{y}  = (x_1, \ldots, x_{n_1}, y_1, \ldots, y_{n_2}) \in
\gf{V_{n_1+n_2}}$. The \textsl{inner product} of $\vec{x},\vec{y} \in
\gf{V_n}$ is denoted by $\vec{x} \cdot \vec{y}$, and the inner product of real
vectors $\vec{x}, \vec{y} \in \bbbr^n$ is denoted by
$\left\langle\vec{x},\vec{y}\right\rangle$. 

One can now define binary functions 
  between this type of vector spaces, whose 
linearity analysis (for robustness-against-attacks purposes) will become very
important. $f: \gf{V_n} \to \gf{GF(2)}$ is called a \textsl{Boolean function} and
$\funct{F}_n$ is the set of all Boolean functions on $\gf{V_n}$. $\funct{L}_n$
is the set of all linear Boolean functions on $\gf{V_n}$: $\funct{L}_n =
\{l_{\vec{u}} \  \fa \vec{u} \in \gf{V_n} \given l_{\vec{u}}(\vec{x})=\vec{u}
\cdot \vec{x}\}$ and $\funct{A}_n$ is the set of all affine Boolean functions
on $\gf{V_n}$. 

It is possible to characterize Boolean functions via alternative and very
useful associated mappings. In the following, some of these mappings are
presented. The real-valued mapping $\chi_{\vec{u}}(\vec{x})={(-1)}^{\sum_{i=1}^{i=n} u_i
  x_i}={(-1)}^{\vec{u} \cdot \vec{x}}$ for $\vec{x}, \vec{u} \in \gf{V_n}$ is
called a \textsl{character}. The character form of $f \in \funct{F}_n$ is
defined as $\chi_f(\vec{x})=(-1)^{f(\vec{x})}$. The Truth Table of $\chi_f$ is
called as the $(1,-1)$-\textsl{sequence vector} or \textsl{sequence vector} of
$f$ and is denoted by $\xi_f \in \bbbr^{2^n}$. 

Let $f \in \funct{F}_n$ be a Boolean function; the \textsl{Walsh Transform} of
$f$ at $\vec{u} \in \gf{V_n}$ is the $n$-dimensional Discrete Fourier
Transform and can be calculated as follows: 

\begin{equation}\label{WalshTransformInner}
\walsh{\chi}_f(\vec{u}) = \left\langle \xi_f, \xi_{l_{\vec{u}}} \right\rangle = 
\sum_{\vec{x} \in \gf{V_n}} (-1)^{f(\vec{x}) + \vec{u} \vec{x}} 
\end{equation}

The \textsl{autocorrelation} of $f \in \funct{F}_n$ with respect to the shift
$\vec{u} \in \gf{V_n}$ is a measure of the statistical
  dependency among the involved variables (indicating robustness against
  randomness-based attacks). It is the cross-correlation 
  of $f$ with itself, denoted by 
$\R_{f}(\vec{u}): \gf{V_n} \to \bbbz$ and defined by \footnote{Most authors omit the factor $\frac{1}{2^n}$}: 
\begin{equation}
\R_f(\vec{u}) = \sum_{\vec{x} \in \gf{V_n}} \chi_f(\vec{x})
\chi_f(\vec{x}+\vec{u}) = \sum_{\vec{x} \in \gf{V_n}} (-1)^{f(\vec{x})+f(\vec{u}+\vec{x})}
\end{equation}

The \textsl{directional derivative} of $f \in \funct{F}_n$ in the direction of $\vec{u} \in \gf{V_n}$ is defined by:
\begin{equation}
    \Delta_{\vec{u}}f(\vec{x}) = f(\vec{x}+\vec{u}) + f(\vec{x}), \  \  \vec{x} \in \gf{V_n} \enspace .
\end{equation}

We shall call the linear kernel of $f$ the set of those vectors $\vec{u}$ such that $\Delta_{\vec{u}}f$ is a constant function.
The linear kernel of any Boolean function is a subspace of $\gf{V_n}$. Any element $\vec{u}$ of the linear kernel of $f$ is said 
to be a linear structure of $f$.

Given  $f \in \funct{F}_n$, a nonzero function $g \in \funct{F}_n$ is called
an annihilator of $f$ if $fg = 0$.

We now extend the scope of the study by considering functions
  between any pair of binary-valued vector spaces.
$F: \gf{V_n} \to \gf{V_m}, \ F(\vec{x}) = (f_1(\vec{x}),\dots,f_{m}(\vec{x}))$
is called a \textsl{Vector Boolean function} and $\funct{F}_{n,m}$ is the set
of all Vector Boolean Functions $F:\gf{V_n} \to \gf{V_m}$. Each $f_i: \gf{V_n}
\to \gf{GF(2)} \ \fa i \in \{1, \ldots, m \}$ is a coordinate function of
$F$. The \textsl{indicator function} of $F \in \funct{F}_{n,m}$, denoted by
$\theta_F : \gf{V_n} \times \gf{V_m} \to \left\{0,1\right\}$, 
is defined in \cite{ChabaudV:94} as:
\begin{equation}\label{IndicatorFunction}
    \theta_F(\vec{x},\vec{y}) = \left\{
	\begin{array}{ll}
		1 & \mbox{if }\vec{y}=F(\vec{x}) \\
		0 & \mbox{if }\vec{y} \neq F(\vec{x})
	\end{array}
\right.
\end{equation}

Again, several mappings associated with a Vector Boolean Functions can be
defined, in similar terms to the binary functions case. Hence, the character 
form of $(\vec{u},\vec{v}) \in \gf{V_n} \times \gf{V_m}$ can be defined as
follows: $\chi_{(\vec{u},\vec{v})}(\vec{x},\vec{y}) = {(-1)}^{\vec{u} \cdot
  \vec{x} + \vec{v} \cdot \vec{y}}$. Similarly, let $F \in \funct{F}_{n,m}$ be
a Vector Boolean function; its \textsl{Walsh 
  Transform} is the two-dimensional Walsh Transform defined by:
\begin{equation}\label{WalshTransformInnerVector}
\walsh{\theta}_F(\vec{u}, \vec{v}) = \sum_{\vec{x} \in \gf{V_n}} \sum_{\vec{y} \in \gf{V_m}} \theta_F(\vec{x},\vec{y}) \chi_{(\vec{u},\vec{v})}(\vec{x},\vec{y})
= \sum_{\vec{x} \in \gf{V_n}} (-1)^{\vec{u}\vec{x} + \vec{v} F(\vec{x})} 
\end{equation}

Also, the \textsl{autocorrelation} of $F \in \funct{F}_{n,m}$
with respect to the shift $(\vec{u},\vec{v}) \in \gf{V_n} \times \gf{V_m}$ is
the cross-correlation of $F$ with itself, denoted by $\R_F(\vec{u},\vec{v}):
\gf{V_n} \times \gf{V_m} \to \bbbz$, so that \cite{fse-Nyberg:94}:  
\begin{equation}\label{eq:AutocorrelationVBF}
\R_F(\vec{u},\vec{v}) = \sum_{\vec{x} \in \gf{V_n}}
\chi_{\vec{v} F}(\vec{x} + \vec{u}) \chi_{\vec{v} F}(\vec{x})
= \sum_{\vec{x} \in \gf{V_n}} (-1)^{\vec{v} F(\vec{x} + \vec{u}) + \vec{v} F(\vec{x})} 
\end{equation}

Let $F \in \funct{F}_{n,m}$ and $\vec{u} \in \gf{V_n}$, then the
\textsl{difference Vector Boolean function} of $F$ in the direction of
$\vec{u} \in \gf{V_n}$, denoted by $\Delta_{\vec{u}}F \in \funct{F}_{n,m}$ is
defined as follows: $\Delta_{\vec{u}}F(\vec{x})=F(\vec{x}+\vec{u})+F(\vec{x}),
\  \vec{x} \in \gf{V_n}$. If the following equality is satisfied:
$\Delta_{\vec{u}}F(\vec{x})=\vec{c}, \  \ \vec{c} \in \gf{V_n} \ \fa \vec{x}
\in \gf{V_n}$ then $\vec{u} \in \gf{V_n}$ is called a linear structure of
$F$. 

Finally, we define the simplifying notation for the maximum
of the absolute values of a 
set of real numbers  $\{a_{\vec{u}\vec{v}}\}_{\vec{u},\vec{v}}$, characterized
by vectors $\vec{u}$ and $\vec{v}$, as: $\max \ (a_{\vec{u}\vec{v}})=
\max_{(\vec{u},\vec{v})}\ \{|a_{\vec{u}\vec{v}}|\}$. Using the same
simplifying notation, we can define the $\stackrel{*}{\max}(\cdot)$ operator on a
set of real numbers  $\{a_{\vec{u}\vec{v}}\}_{\vec{u},\vec{v}}$, as:
$\stackrel{*}{\max}(a_{\vec{u}\vec{v}})=\max_{(\vec{u},\vec{v})\neq(\vec{0},\vec{0})}\{|a_{\vec{u}\vec{v}}|\}$.
This notation will be used in some criteria definitions. 

\section{Design Philosophy}

The core of VBF library is the VBF class which represents Vector Boolean
Functions whose data members and member functions make use of the NTL modules
listed in Table \ref{tab:NTLModules}. However, some new cryptography-related
member functions were added to the previous modules. Besides, new modules which are not present in NTL, are defined and they are listed in Table~\ref{tab:NewModules}.  

\begin{table}[htbp]%
\caption{NTL modules used in VBF\label{tab:NTLModules}}{%
\begin{tabular}{|l|l|}
\hline
\em{CLASS NAME} & \em{DESCRIPTION} \\\hline
\textsl{GF2} & Galois Field of order $2$ denoted by $\gf{GF(2)}$ \\\hline
\textsl{vec\_GF2} & Vectors over $\gf{GF(2)}$ \\\hline
\textsl{mat\_GF2} & Matrices over $\gf{GF(2)}$ \\\hline
\textsl{RR} & Arbitrary-precision floating point numbers \\\hline
\textsl{vec\_RR} & Vectors over reals \\\hline
\textsl{mat\_RR} & Matrices over reals \\\hline
\textsl{ZZ} & Signed, arbitrary length integers \\\hline
\textsl{vec\_ZZ} & Vectors over integers \\\hline
\textsl{mat\_ZZ} & Matrices over integers \\\hline
\textsl{GF2X} & Implements polynomial arithmetic modulo $2$ \\\hline
\textsl{GF2E} & Polynomials in $F_2[X]$ modulo a polynomial $P$ \\\hline
\textsl{GF2EX} & Polynomials over $\gf{GF2E}$ \\\hline
\textsl{vec\_GF2E} & Vectors over $\gf{GF2E}$ \\\hline
\end{tabular}}
\end{table}%

Note that the modulus $P$ in $\gf{GF2E}$ may be any polynomial with degree
greater than $0$, not necessarily irreducible. Objects of the class $\gf{GF2E}$ are
represented as a $\gf{GF2X}$ of degree less than the degree of $P$. $\gf{GF2EX}$
can be used, for example, for arithmetic in $\gf{GF(2^n)[X]}$. 

\begin{table}[htbp]%
\caption{New modules created for VBF\label{tab:NewModules}}{%
\begin{tabular}{|l|l|}
\hline
\em{CLASS NAME} & \em{DESCRIPTION} \\\hline
\textsl{pol} & Polynomial in ANF of a Boolean Function \\\hline
\textsl{vec\_pol} & Polynomials in ANF of a Vector Boolean Function \\\hline
\end{tabular}}
\end{table}%

The main file in the library, called \textsl{VBF.h} has the definitions
of the objects described in the next chapters.



