Difference between revisions of "Vectorial Boolean Functions"

From Boolean Functions
Jump to: navigation, search
(Cryptanalytic attacks)
Line 1: Line 1:
 
= Introduction =
 
= Introduction =
Vectorial Boolean functions are functions from the vectorspace <math>\mathbb{F}_2^n</math>, of all binary vectors of length <math>n</math>, to the vectorspace <math>\mathbb{F}_2^m</math>, for some positive integers <math>n</math> and <math>m</math>, where <math>\mathbb{F}_2</math> is the finite field with two elements.
+
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.
 +
 
 +
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>.
  
 
== Cryptanalytic attacks ==
 
== Cryptanalytic attacks ==
This is a very good book <ref name="our_ref">Claude Carlet, ''Boolean functions for cryptography and error correcting codes'', Boolean models and methods in mathematics, computer science, and engineering, 2, pp. 257-397, 2010</ref>.
+
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.
  
Let's refer to the same book again <ref name="our_ref" />.
+
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 =
 
= Generalities on Boolean functions =

Revision as of 21:26, 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

Representations