Vectorial Boolean Functions: Difference between revisions
No edit summary |
No edit summary |
||
| 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^ | 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 | 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^ | 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^ | 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^ | 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 21:02, 30 December 2018
Introduction
Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^n} be the vector space of dimension Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} over the finite field Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2} with two elements. Functions from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^n} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^m} are called Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -functions or simply vectorial Boolean functions when the dimensions of the vector spaces are implicit or irrelevant.
Any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} can be written as a vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F = (f_1, f_2, \ldots f_n)} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -dimensional Boolean functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1, f_2, \ldots f_n} which are called the coordinate functions of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} .
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m} is the integer-valued function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_F : \mathbb{F}_2^n \times \mathbb{F}_2^m} defined by
It can be observed that the Walsh transform of some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{G_F}} defined as
The Walsh spectrum of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is the multi-set of all the values of its Walsh transform for all pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v) \in \mathbb{F}_2^n \times {\mathbb{F}_2^m}^*} . The extended Walsh spectrum of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is the multi-set of the absolute values of its Walsh transform, and the Walsh support of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is the set of pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v)} for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_F(u,v) \ne 0} .
Representations
Vectorial Boolean functions can be represented in a number of different ways.
Algebraic Normal Form
An Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} can be uniquely represented as a polynomial with coefficients in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^m} of the form
where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\cal P}(N)} is the power set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = \{ 1, \ldots, n \}} and the coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_I} belong to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^m} . This representation is known as the algebraic normal form (ANF) of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . The algebraic degree of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} , denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d^\circ(F)} 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 .
