# Introduction

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

Any $(n,m)$ -function $F$ can be written as a vector $F=(f_{1},f_{2},\ldots f_{n})$ of $m$ -dimensional Boolean functions $f_{1},f_{2},\ldots f_{n}$ which are called the coordinate functions of $F$ .

## 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 $F:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}$ is the integer-valued function $W_{F}:\mathbb {F} _{2}^{n}\times \mathbb {F} _{2}^{m}$ defined by

$W_{F}(u,v)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{v\cdot F(x)+u\cdot x}$ It can be observed that the Walsh transform of some $F$ is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function $1_{G_{F}}$ defined as

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

The Walsh spectrum of $F$ is the multi-set of all the values of its Walsh transform for all pairs $(u,v)\in \mathbb {F} _{2}^{n}\times {\mathbb {F} _{2}^{m}}^{*}$ . The extended Walsh spectrum of $F$ is the multi-set of the absolute values of its Walsh transform, and the Walsh support of $F$ is the set of pairs $(u,v)$ for which $W_{F}(u,v)\neq 0$ .

## Representations

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

### Algebraic Normal Form

An $\displaystyle (n,m)$ -function $F$ can be uniquely represented as a polynomial with coefficients in $\mathbb {F} _{2}^{m}$ of the form

$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},$ where $\displaystyle {\cal P}(N)$ is the power set of $\displaystyle N = \{ 1, \ldots, n \}$ and the coefficients $\displaystyle a_I$ belong to $\mathbb {F} _{2}^{m}$ . This representation is known as the algebraic normal form (ANF) of $\displaystyle F$ . The algebraic degree of $\displaystyle F$ , denoted $d^{\circ }(F)$ is then defined as the global degree of its ANF, i.e.

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

and is equal to the maximal algebraic degree of the coordinate functions of $\displaystyle F$ .

### Univariate Representation

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

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

This is the univariate representation of $\displaystyle F$ .

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

$\max _{j=0,\dots ,2^{n}-1/\,\delta _{j}\neq 0}w_{2}(j).$ ## Basic Properties of Vectorial Boolean Functions

### Balanced Functions

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

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