Vectorial Boolean Functions

From Boolean Functions
Revision as of 21:26, 30 December 2018 by Nikolay (talk | contribs)
Jump to: navigation, search


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