Vectorial Boolean Functions

From Boolean
Revision as of 14:57, 23 September 2019 by Ivi062 (talk | contribs)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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;
  • 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 [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]

Equivalence Relations

Two vectorial Boolean functions [math]\displaystyle{ F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m }[/math] are called

  • affine (linear) equivalent if there exist [math]\displaystyle{ A_1,A_2 }[/math] affine (linear) permutations of [math]\displaystyle{ \mathbb{F}_2^m }[/math] and [math]\displaystyle{ \mathbb{F}_2^n }[/math] respectively, such that [math]\displaystyle{ F'=A_1\circ F\circ A_2 }[/math];
  • extended affine equivalent (shortly EA-equivalent) if there exists [math]\displaystyle{ A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m }[/math] affine such that [math]\displaystyle{ F'=F''+A }[/math], with [math]\displaystyle{ F'' }[/math] affine equivalent to [math]\displaystyle{ F }[/math];
  • Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation [math]\displaystyle{ \mathcal{L} }[/math] of [math]\displaystyle{ \mathbb{F}_2^n\times\mathbb{F}_2^m }[/math] such that the image of the graph of [math]\displaystyle{ F }[/math] is the graph of [math]\displaystyle{ F' }[/math], i.e. [math]\displaystyle{ \mathcal{L}(G_F)=G_{F'} }[/math] with [math]\displaystyle{ G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\} }[/math] and [math]\displaystyle{ G_{F'}=\{ (x,F'(x)) : x\in\mathbb{F}_2^n\} }[/math].

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].