Vectorial Boolean Functions: Difference between revisions
No edit summary |
NikiSpithaki (talk | contribs) |
||
| (7 intermediate revisions by 3 users not shown) | |||
| 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| 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 12: | Line 12: | ||
* the higher order differential attack; to resist it, an S-box must have high [[algebraic degree]]; | * 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; | * 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. | * algebraic attacks; | ||
* boomerang attack, introduced by Wagner; to resist it, an S-box must have low [[boomerang uniformity]]. | |||
= Generalities on Boolean functions = | = Generalities on Boolean functions = | ||
| Line 18: | Line 19: | ||
== 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 33: | ||
</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>. | |||
=== Univariate Representation === | |||
If we identify the vector space <math>\mathbb{F}_2^n</math> with the finite field <math>\mathbb{F}_{2^n}</math> with <math>2^n</math> elements, then any <math>(n,n)</math>-function can be uniquely represented as univariate polynomial over <math>\mathbb{F}_{2^n}</math> of degree at most <math>2^n-1</math> taking the form | |||
<div class="equation"><math> | |||
F(x)=\sum_{j=0}^{2^n-1}\delta_jx^j~,~~\delta_j\in \Bbb{F}_{2^n}. | |||
</math></div> | |||
This is the <span class="definition">univariate representation</span> of <math>F</math>. | |||
The algebraic degree of <math>F</math> can be expressed using the 2-weight of the exponents of the univariate representation. Given a positive integer <math>j</math>, its <span class="definition">2-weight</span> is the number of summands in its representation as a sum of powers of two; that is, if we write <math>j = \sum_{i = 0}^{n-1} j_s \cdot 2^s</math> for <math>j_s \in \{0,1\}</math>, then its 2-weigt is <math>w_2(j) = \sum_{i = 0}^{n-1} j_s</math>. The <span class="definition">algebraic degree</span> of <math>F</math> can the be written as | |||
<div class="equation><math> | |||
\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j). | |||
</math></div> | |||
== Basic Properties of Vectorial Boolean Functions == | |||
=== Balanced Functions === | |||
An <math>(n,m)</math>-function <math>F</math> is called <span class="definition">balanced</span> if it takes every value of <math>\mathbb{F}_2^m</math> precisely <math>2^{n-m}</math> times. In particular, an <math>(n,n)</math>-function is balanced if and only if it is a permutation. | |||
<div class="proposition"> | |||
An <math>(n,m)</math>-function <math>F</math> is balanced if and only if its component functions are balanced, i.e. if and only if <math>v \cdot F</math> is balanced for every <math>v \in {\mathbb{F}_2^m}^*</math>. | |||
Latest revision as of 13:01, 8 October 2024
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 -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;
- boomerang attack, introduced by Wagner; to resist it, an S-box must have low boomerang uniformity.
Generalities on Boolean functions
Walsh transform
The Walsh transform of 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 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 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} .
Univariate Representation
If we identify the vector space 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} with 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^n}} with 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 2^n} elements, then 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,n)} -function can be uniquely represented as univariate polynomial over 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}} of degree at most 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 2^n-1} taking the form
This is the univariate representation 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} can be expressed using the 2-weight of the exponents of the univariate representation. Given a positive integer 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 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 (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 j = \sum_{i = 0}^{n-1} j_s \cdot 2^s} for 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 j_s \in \{0,1\}} , then its 2-weigt is 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_2(j) = \sum_{i = 0}^{n-1} j_s} . 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} can the be written as
Basic Properties of Vectorial Boolean Functions
Balanced Functions
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} is called balanced if it takes every value 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 \mathbb{F}_2^m} precisely 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 2^{n-m}} times. In particular, an -function is balanced if and only if it is a permutation.
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} is balanced if and only if its component functions are balanced, i.e. if and only if 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 v \cdot F} is balanced for every .
