Vectorial Boolean Functions

Introduction

Let ${𝔽}_2^n$ be the vector space of dimension $n$ over the finite field ${𝔽}_2$ with two elements. Functions from ${𝔽}_2^n$ to ${𝔽}_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,\dots f_n)$ of $m$-dimensional Boolean functions $f_1,f_2,\dots 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:{𝔽}_2^n\to {𝔽}_2^m$ is the integer-valued function $W_F:{𝔽}_2^n\times {𝔽}_2^m$ defined by

$W_F(u,v)=\sum _{x\in {𝔽}_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

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

The Walsh spectrum of $F$ is the multi-set of all the values of its Walsh transform for all pairs $(u,v)\in {𝔽}_2^n\times {{𝔽}_2^m}^{\ast }$. 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)\ne 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 ${𝔽}_2^m$ of the form

$F(x)=\sum _{I\in 𝒫(N)}{a}_I\left(\prod _{i\in I}{x}_i\right)=\sum _{I\in 𝒫(N)}{a}_I{x}^I,$

where $𝒫(N)$ is the power set of $N=\{1,\dots ,n\}$ and the coefficients $a_I$ belong to ${𝔽}_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.

$d^{\circ }(F)=max\{|I|/a_I\ne (0,\dots ,0);I\in 𝒫(N)\}$

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

Univariate Representation

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

$F(x)=\sum _{j=0}^{2^n-1}{\delta }_j{x}^j,{\delta }_j\in {𝔽}_{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 $j=\sum _{i=0}^{n-1}{j}_s\cdot 2^s$ for $j_s\in \{0,1\}$, then its 2-weigt is $w_2(j)=\sum _{i=0}^{n-1}{j}_s$. The algebraic degree of $F$ can the be written as

$\underset{j=0,\dots ,2^n-1/{\delta }_j\ne 0}{max}{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 ${𝔽}_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 {{𝔽}_2^m}^{\ast }$.