Vectorial Boolean Functions

From Boolean Functions
Revision as of 20:24, 10 February 2019 by Nikolay (talk | contribs)
Jump to: navigation, search

Introduction

Let be the vector space of dimension over the finite field with two elements. Functions from to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^m} 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1_{G_F}(x,y) = \begin{cases} 1 & F(x) = y \\ 0 & F(x) \ne y. \end{cases} }

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function can be uniquely represented as a polynomial with coefficients in of the form

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {\cal P}(N)} is the power set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle N = \{ 1, \ldots, n \}} and the coefficients Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_I} belong to . This representation is known as the algebraic normal form (ANF) of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} . The algebraic degree of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} , denoted is then defined as the global degree of its ANF, i.e.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d^\circ(F)=\ max \{|I|/\, a_I\neq (0,\dots ,0); I\in {\cal P}(N)\} }

and is equal to the maximal algebraic degree of the coordinate functions of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} .

Univariate Representation

If we identify the vector space with the finite field Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{2^n}} with elements, then any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (n,n)} -function can be uniquely represented as univariate polynomial over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{2^n}} of degree at most taking the form

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F(x)=\sum_{j=0}^{2^n-1}\delta_jx^j~,~~\delta_j\in \Bbb{F}_{2^n}. }

This is the univariate representation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} .

The algebraic degree of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F} can be expressed using the 2-weight of the exponents of the univariate representation. Given a positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j} , its 2-weight is the number of summands in its representation as a sum of powers of two; that is, if we write Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j = \sum_{i = 0}^{n-1} j_s \cdot 2^s} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j_s \in \{0,1\}} , then its 2-weigt is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w_2(j) = \sum_{i = 0}^{n-1} j_s} . The algebraic degree of can the be written as

Basic Properties of Vectorial Boolean Functions

Balanced Functions

An -function is called balanced if it takes every value of precisely times. In particular, an -function is balanced if and only if it is a permutation.

An -function is balanced if and only if its component functions are balanced, i.e. if and only if is balanced for every .