Vectorial Boolean Functions

Introduction

Let <math>\mathbb{F}_2^n</math> be the vector space of dimension <math>n</math> over the finite field <math>\mathbb{F}_2</math> with two elements. Functions from <math>\mathbb{F}_2^n</math> to <math>\mathbb{F}_2^m</math> are called <math>(n,m)</math>-functions or simply vectorial Boolean functions when the dimensions of the vector spaces are implicit or irrelevant.

Any <math>(n,m)</math>-function <math>F</math> can be written as a vector <math>F = (f_1, f_2, \ldots f_n)</math> of <math>m</math>-dimensional Boolean functions <math>f_1, f_2, \ldots f_n</math> which are called the coordinate functions of <math>F</math>.

Cryptanalytic attacks

Vectorial Boolean functions, also referred to as "S-boxes", or "Substitution boxes", in the context of cryptography, are a fundamental building block of block ciphers and are crucial to their security: more precisely, the resistance of the block cipher to cryptanalytic attacks directly depends on the properties of the S-boxes used in its construction.

The main types of cryptanalytic attacks that result in the definition of design criteria for S-boxes are the following:

• the differential attack introduced by Biham and Shamir; to resist it, an S-box must have low differential uniformity;
• the linear attack introduced by Matsui; to resist it, an S-box must have high nonlinearity;
• the higher order differential attack; to resist it, an S-box must have high algebraic degree;
• the interpolation attack; to resist it, the univariate representation of an S-box must have high degree, and its distance to the set of low univariate degree functions must be large;
• algebraic attacks.

Generalities on Boolean functions

Walsh transform

The Walsh transform of <math>F : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m</math> is the integer-valued function <math>W_F : \mathbb{F}_2^n \times \mathbb{F}_2^m</math> defined by

<math>

W_F(u,v) = \sum_{x \in \mathbb{F}_2^n} (-1)^{v \cdot F(x) + u \cdot x}

</math>

It can be observed that the Walsh transform of some <math>F</math> is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function <math>1_{G_F}</math> defined as

<math>

1_{G_F}(x,y) = \begin{cases} 1 & F(x) = y \\ 0 & F(x) \ne y. \end{cases}

</math>

The Walsh spectrum of <math>F</math> is the multi-set of all the values of its Walsh transform for all pairs <math>(u,v) \in \mathbb{F}_2^n \times {\mathbb{F}_2^m}^*</math>. The extended Walsh spectrum of <math>F</math> is the multi-set of the absolute values of its Walsh transform, and the Walsh support of <math>F</math> is the set of pairs <math>(u,v)</math> for which <math>W_F(u,v) \ne 0</math>.

Representations

Vectorial Boolean functions can be represented in a number of different ways.

Algebraic Normal Form

An <math>(n,m)</math>-function <math>F</math> can be uniquely represented as a polynomial with coefficients in <math>\mathbb{F}_2^m</math> of the form

<math>

F(x)=\sum_{I \in {\cal P}(N)} a_I\, \left(\prod_{i\in I}x_i\right)=\sum_{I\in {\cal P}(N)} a_I\, x^I,

</math>

where <math>{\cal P}(N)</math> is the power set of <math>N = \{ 1, \ldots, n \}</math> and the coefficients <math>a_I</math> belong to <math>\mathbb{F}_2^m</math>. This representation is known as the algebraic normal form (ANF) of <math>F</math>. The algebraic degree of <math>F</math>, denoted <math>d^\circ(F)</math> is then defined as the global degree of its ANF, i.e.

<math>

d^\circ(F)=\ max \{|I|/\, a_I\neq (0,\dots ,0); I\in {\cal P}(N)\}

</math>

and is equal to the maximal algebraic degree of the coordinate functions of <math>F</math>.

Univariate Representation

If we identify the vector space <math>\mathbb{F}_2^n</math> with the finite field <math>\mathbb{F}_{2^n}</math> with <math>2^n</math> elements, then any <math>(n,n)</math>-function can be uniquely represented as univariate polynomial over <math>\mathbb{F}_{2^n}</math> of degree at most <math>2^n-1</math> taking the form

<math>

F(x)=\sum_{j=0}^{2^n-1}\delta_jx^j~,~~\delta_j\in \Bbb{F}_{2^n}.

</math>

This is the univariate representation of <math>F</math>.

The algebraic degree of <math>F</math> can be expressed using the 2-weight of the exponents of the univariate representation. Given a positive integer <math>j</math>, its 2-weight is the number of summands in its representation as a sum of powers of two; that is, if we write <math>j = \sum_{i = 0}^{n-1} j_s \cdot 2^s</math> for <math>j_s \in \{0,1\}</math>, then its 2-weigt is <math>w_2(j) = \sum_{i = 0}^{n-1} j_s</math>. The algebraic degree of <math>F</math> can the be written as

<math>

\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).

</math>

Basic Properties of Vectorial Boolean Functions

Balanced Functions

An <math>(n,m)</math>-function <math>F</math> is called balanced if it takes every value of <math>\mathbb{F}_2^m</math> precisely <math>2^{n-m}</math> times. In particular, an <math>(n,n)</math>-function is balanced if and only if it is a permutation.

An <math>(n,m)</math>-function <math>F</math> is balanced if and only if its component functions are balanced, i.e. if and only if <math>v \cdot F</math> is balanced for every <math>v \in {\mathbb{F}_2^m}^*</math>.