Vectorial Boolean Functions

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 $\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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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;
• boomerang attack, introduced by Wagner; to resist it, an S-box must have low boomerang uniformity.

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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1_{G_{F}}} defined as

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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 $(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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\cal {P}}(N)} is the power set of $N=\{1,\ldots ,n\}$ and the coefficients $a_{I}$ belong to $\mathbb {F} _{2}^{m}$. This representation is known as the algebraic normal form (ANF) of $F$. The algebraic degree of $F$, denoted $d^{\circ }(F)$ is then defined as the global degree of its ANF, i.e.

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $F$.

Univariate Representation

If we identify the vector space $\mathbb {F} _{2}^{n}$ with the finite field $\mathbb {F} _{2^{n}}$ with $2^{n}$ elements, then any $(n,n)$-function can be uniquely represented as univariate polynomial over $\mathbb {F} _{2^{n}}$ of degree at most Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{n}-1} taking the form

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $F$.

The algebraic degree of $F$ can be expressed using the 2-weight of the exponents of the univariate representation. Given a positive integer $j$, its 2-weight is the number of summands in its representation as a sum of powers of two; that is, if we write Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle j=\sum _{i=0}^{n-1}j_{s}\cdot 2^{s}} for $j_{s}\in \{0,1\}$, then its 2-weigt is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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).$

Equivalence Relations

Two vectorial Boolean functions $F,F':\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}$ are called

• affine (linear) equivalent if there exist $A_{1},A_{2}$ affine (linear) permutations of $\mathbb {F} _{2}^{m}$ and $\mathbb {F} _{2}^{n}$ respectively, such that $F'=A_{1}\circ F\circ A_{2}$;
• extended affine equivalent (shortly EA-equivalent) if there exists Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}} affine such that $F'=F''+A$, with $F''$ affine equivalent to $F$;
• Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {L}}} of $\mathbb {F} _{2}^{n}\times \mathbb {F} _{2}^{m}$ such that the image of the graph of $F$ is the graph of $F'$, i.e. ${\mathcal {L}}(G_{F})=G_{F'}$ with $G_{F}=\{(x,F(x)):x\in \mathbb {F} _{2}^{n}\}$ and $G_{F'}=\{(x,F'(x)):x\in \mathbb {F} _{2}^{n}\}$.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{n-m}} times. In particular, an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} -function is balanced if and only if it is a permutation.

An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is balanced if and only if its component functions are balanced, i.e. if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v \cdot F} is balanced for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v \in {\mathbb{F}_2^m}^*} .