2. 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.

2.1. Functions available in VBF

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

  1. Vector Boolean Function representations and characterizations
  2. Cryptographic criteria calculation
  3. Constructions and operations over Vector Boolean functions

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

2.2. Conventions used in this manual

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

$ command

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).

2.3. Software implementation

The package included consists of:

  1. Derived classes inherited from NTL base classes which add new functions on top of them:
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
  1. Main class (VBF.h) with the functions and other .h files,
  2. A makefile to ease the compilation of example (Makefile),
  3. A set of files associated with the decimal representation of KASUMI [KASUMI:05] S-boxes (S7.dec and S9.dec).

The Output files can be found within “KASUMI Analysis” in the “Analysis of other cryptographic algorithms” menu at `http://vbflibrary.tk`_.

2.4. 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.

2.5. Installation

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

  1. Download the lastest version of the library from VBF source code URL and place it in the working directory. You should see the example program, input files and the “*.h” files.
  2. Obtain NTL library source code. To obtain the source code and documentation for NTL, download ntl-xxx.tar.gz from Download NTL library, placing it in a different directory.
  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):
$ cd ntl-xxx/src
$ ./configure

The execution of 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.

Disable GMP

If you really do not want to use GMP, you can pass the option NTL_GMP_LIP=off to configure. More information on A Tour of NTL: Obtaining and Installing NTL for UNIX
  1. Build NTL:
$ make
$ make check
$ make install

The make execution in the directory 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 make check. Lastly, 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.

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

2.6. 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 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 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 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 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)-sequence vector or 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 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*} \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 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 [1]:

\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 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} \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 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 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 [ChabaudV:94] as:

(1)\begin{equation*} \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 Walsh Transform is the two-dimensional Walsh Transform defined by:

(2)\begin{equation*} \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 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 [fse-Nyberg:94]:

(3)\begin{equation*} \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 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.

Footnotes

[1]Most authors omit the factor \frac{1}{2^n}

2.7. 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 NTL Modules. 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 New Modules.

NTL modules used in VBF
CLASS NAME DESCRIPTION
GF2 Galois Field of order 2 denoted by \gf{GF(2)}
vec_GF2 Vectors over \gf{GF(2)}
mat_GF2 Matrices over \gf{GF(2)}
RR Arbitrary-precision floating point numbers
vec_RR Vectors over reals
mat_RR Matrices over reals
ZZ Signed, arbitrary length integers
vec_ZZ Vectors over integers
mat_ZZ Matrices over integers
GF2X Implements polynomial arithmetic modulo 2
GF2E Polynomials in F_2[X] modulo a polynomial P
GF2EX Polynomials over \gf{GF2E}
vec_GF2E Vectors over \gf{GF2E}

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]}.

New modules created for VBF
CLASS NAME DESCRIPTION
pol Polynomial in ANF of a Boolean Function
vec_pol Polynomials in ANF of a Vector Boolean Function

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