# Introduction

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

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

${\displaystyle 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 ${\displaystyle F}$ is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function ${\displaystyle 1_{G_{F}}}$ defined as

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

The Walsh spectrum of ${\displaystyle F}$ is the multi-set of all the values of its Walsh transform for all pairs ${\displaystyle (u,v)\in \mathbb {F} _{2}^{n}\times {\mathbb {F} _{2}^{m}}^{*}}$. The extended Walsh spectrum of ${\displaystyle F}$ is the multi-set of the absolute values of its Walsh transform, and the Walsh support of ${\displaystyle F}$ is the set of pairs ${\displaystyle (u,v)}$ for which ${\displaystyle 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 ${\displaystyle F}$ can be uniquely represented as a polynomial with coefficients in ${\displaystyle \mathbb {F} _{2}^{m}}$ of the form

${\displaystyle 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 ${\displaystyle \mathbb {F} _{2}^{m}}$. This representation is known as the algebraic normal form (ANF) of ${\displaystyle F}$. The algebraic degree of ${\displaystyle F}$, denoted ${\displaystyle 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 ${\displaystyle \mathbb {F} _{2}^{n}}$ with the finite field ${\displaystyle \mathbb {F} _{2^{n}}}$ with ${\displaystyle 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 ${\displaystyle 2^{n}-1}$ taking the form

${\displaystyle F(x)=\sum _{j=0}^{2^{n}-1}\delta _{j}x^{j}~,~~\delta _{j}\in {\mathbb {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 ${\displaystyle F}$ can the be written as

${\displaystyle \max _{j=0,\dots ,2^{n}-1/\,\delta _{j}\neq 0}w_{2}(j).}$

TODO

## Basic Properties of Vectorial Boolean Functions

### Balanced Functions

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

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

TODO

TODO