Difference between revisions of "Vectorial Boolean Functions"

From Boolean Functions
Jump to: navigation, search
Line 1: Line 1:
 
= Introduction =
 
= Introduction =
Let <math>\mathbb{F}_2^n</math> be the vector space of dimension <math>n</math> over the finite field <math>\mathbb{F}_2</math> with two elements. Functions from <math>\mathbb{F}_2^m</math> to <math>\mathbb{F}_2^n</math> are called <span class="definition"><math>(m,n)</math>-functions</span> or simply <span class="definition">vectorial Boolean functions</span> when the dimensions of the vector spaces are implicit or irrelevant.
+
Let <math>\mathbb{F}_2^n</math> be the vector space of dimension <math>n</math> over the finite field <math>\mathbb{F}_2</math> with two elements. Functions from <math>\mathbb{F}_2^n</math> to <math>\mathbb{F}_2^m</math> are called <span class="definition"><math>(n,m)</math>-functions</span> or simply <span class="definition">vectorial Boolean functions</span> when the dimensions of the vector spaces are implicit or irrelevant.
  
Any <math>(m,n)</math>-function <math>F</math> can be written as a vector <math>F = (f_1, f_2, \ldots f_m)</math> of <math>n</math>-dimensional [[Boolean functions]] <math>f_1, f_2, \ldots f_m</math> which are called the <span class="definition">coordinate functions</span> of <math>F</math>.
+
Any <math>(n,m)</math>-function <math>F</math> can be written as a vector <math>F = (f_1, f_2, \ldots f_n)</math> of <math>m</math>-dimensional [[Boolean functions]] <math>f_1, f_2, \ldots f_n</math> which are called the <span class="definition">coordinate functions</span> of <math>F</math>.
  
 
== Cryptanalytic attacks ==
 
== Cryptanalytic attacks ==
Line 18: Line 18:
 
== Walsh transform ==
 
== Walsh transform ==
  
The <span class="definition">Walsh transform</span> of <math>F : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n</math> is the integer-valued function <math>W_F : \mathbb{F}_2^m \times \mathbb{F}_2^n</math> defined by
+
The <span class="definition">Walsh transform</span> of <math>F : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m</math> is the integer-valued function <math>W_F : \mathbb{F}_2^n \times \mathbb{F}_2^m</math> defined by
  
 
<div class="equation><math>
 
<div class="equation><math>
W_F(u,v) = \sum_{x \in \mathbb{F}_2^m} (-1)^{v \cdot F(x) + u \cdot x}
+
W_F(u,v) = \sum_{x \in \mathbb{F}_2^n} (-1)^{v \cdot F(x) + u \cdot x}
 
</math></div>
 
</math></div>
  
Line 32: Line 32:
 
</math></div>
 
</math></div>
  
The <span class="definition">Walsh spectrum</span> of <math>F</math> is the multi-set of all the values of its Walsh transform for all pairs <math>(u,v) \in \mathbb{F}_2^m \times {\mathbb{F}_2^n}^*</math>. The <span class="definition">extended Walsh spectrum</span> of <math>F</math> is the multi-set of the absolute values of its Walsh transform, and the <span class="definition">Walsh support</span> of <math>F</math> is the set of pairs <math>(u,v)</math> for which <math>W_F(u,v) \ne 0</math>.
+
The <span class="definition">Walsh spectrum</span> of <math>F</math> is the multi-set of all the values of its Walsh transform for all pairs <math>(u,v) \in \mathbb{F}_2^n \times {\mathbb{F}_2^m}^*</math>. The <span class="definition">extended Walsh spectrum</span> of <math>F</math> is the multi-set of the absolute values of its Walsh transform, and the <span class="definition">Walsh support</span> of <math>F</math> is the set of pairs <math>(u,v)</math> for which <math>W_F(u,v) \ne 0</math>.
 +
 
 
== Representations ==
 
== Representations ==
 +
 +
Vectorial Boolean functions can be represented in a number of different ways.
 +
 +
=== Algebraic Normal Form ===
 +
 +
An <math>(n,m)</math>-function <math>F</math> can be uniquely represented as a polynomial with coefficients in <math>\mathbb{F}_2^m</math> of the form
 +
 +
<div class="equation><math>
 +
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></div>
 +
 +
where <math>{\cal P}(N)</math> is the power set of <math>N = \{ 1, \ldots, n \}</math> and the coefficients <math>a_I</math> belong to <math>\mathbb{F}_2^m</math>. This representation is known as the <span class="definition">algebraic normal form (ANF)</span> of <math>F</math>. The <span class="definition">algebraic degree</span> of <math>F</math>, denoted <math>d^\circ(F)</math> is then defined as the global degree of its ANF, i.e.
 +
 +
<div class="equation><math>
 +
d^\circ(F)=\ max \{|I|/\, a_I\neq (0,\dots ,0); I\in {\cal P}(N)\}
 +
</math></div>
 +
 +
and is equal to the maximal algebraic degree of the coordinate functions of <math>F</math>.

Revision as of 22:02, 30 December 2018

Introduction

Let be the vector space of dimension over the finite field with two elements. Functions from to are called -functions or simply vectorial Boolean functions when the dimensions of the vector spaces are implicit or irrelevant.

Any -function can be written as a vector of -dimensional Boolean functions which are called the coordinate functions of .

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 is the integer-valued function defined by

It can be observed that the Walsh transform of some is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function defined as

The Walsh spectrum of is the multi-set of all the values of its Walsh transform for all pairs . The extended Walsh spectrum of is the multi-set of the absolute values of its Walsh transform, and the Walsh support of is the set of pairs for which .

Representations

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

Algebraic Normal Form

An -function can be uniquely represented as a polynomial with coefficients in of the form

where is the power set of and the coefficients belong to . This representation is known as the algebraic normal form (ANF) of . The algebraic degree of , denoted is then defined as the global degree of its ANF, i.e.

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