Vectorial Boolean Functions

Introduction

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

Any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] can be written as a vector [math]\displaystyle{ F = (f_1, f_2, \ldots f_n) }[/math] of [math]\displaystyle{ m }[/math]-dimensional Boolean functions [math]\displaystyle{ f_1, f_2, \ldots f_n }[/math] which are called the coordinate functions of [math]\displaystyle{ F }[/math].

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 [math]\displaystyle{ F : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m }[/math] is the integer-valued function [math]\displaystyle{ W_F : \mathbb{F}_2^n \times \mathbb{F}_2^m }[/math] defined by

[math]\displaystyle{ W_F(u,v) = \sum_{x \in \mathbb{F}_2^n} (-1)^{v \cdot F(x) + u \cdot x} }[/math]

It can be observed that the Walsh transform of some [math]\displaystyle{ F }[/math] is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function [math]\displaystyle{ 1_{G_F} }[/math] defined as

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

The Walsh spectrum of [math]\displaystyle{ F }[/math] is the multi-set of all the values of its Walsh transform for all pairs [math]\displaystyle{ (u,v) \in \mathbb{F}_2^n \times {\mathbb{F}_2^m}^* }[/math]. The extended Walsh spectrum of [math]\displaystyle{ F }[/math] is the multi-set of the absolute values of its Walsh transform, and the Walsh support of [math]\displaystyle{ F }[/math] is the set of pairs [math]\displaystyle{ (u,v) }[/math] for which [math]\displaystyle{ W_F(u,v) \ne 0 }[/math].

Representations

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

Algebraic Normal Form

An [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] can be uniquely represented as a polynomial with coefficients in [math]\displaystyle{ \mathbb{F}_2^m }[/math] of the form

[math]\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, }[/math]

where [math]\displaystyle{ {\cal P}(N) }[/math] is the power set of [math]\displaystyle{ N = \{ 1, \ldots, n \} }[/math] and the coefficients [math]\displaystyle{ a_I }[/math] belong to [math]\displaystyle{ \mathbb{F}_2^m }[/math]. This representation is known as the algebraic normal form (ANF) of [math]\displaystyle{ F }[/math]. The algebraic degree of [math]\displaystyle{ F }[/math], denoted [math]\displaystyle{ d^\circ(F) }[/math] is then defined as the global degree of its ANF, i.e.

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

and is equal to the maximal algebraic degree of the coordinate functions of [math]\displaystyle{ F }[/math].

Univariate Representation

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

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

This is the univariate representation of [math]\displaystyle{ F }[/math].

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

[math]\displaystyle{ \max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j). }[/math]

Multi-dimensional Walsh Transform

TODO

Basic Properties of Vectorial Boolean Functions

Balanced Functions

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

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

Covering Sequences

TODO

Algebraic Immunity

TODO