# 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}^{m}$ to $\mathbb {F} _{2}^{n}$ are called $(m,n)$ -functions or simply vectorial Boolean functions when the dimensions of the vector spaces are implicit or irrelevant.

Any $(m,n)$ -function $F$ can be written as a vector $F=(f_{1},f_{2},\ldots f_{m})$ of $n$ -dimensional Boolean functions $f_{1},f_{2},\ldots f_{m}$ 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}^{m}\rightarrow \mathbb {F} _{2}^{n}$ is the integer-valued function $W_{F}:\mathbb {F} _{2}^{m}\times \mathbb {F} _{2}^{n}$ defined by

$W_{F}(u,v)=\sum _{x\in \mathbb {F} _{2}^{m}}(-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

$1_{G_{F}}(x,y)={\begin{cases}1&F(x)=y\\0&F(x)\neq 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}^{m}\times {\mathbb {F} _{2}^{n}}^{*}$ . 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$ .