Vectorial Boolean Functions - Revision history

NikiSpithaki: /* Univariate Representation */

2024-10-08T13:01:32Z

Univariate Representation

← Older revision		Revision as of 13:01, 8 October 2024
Line 59:		Line 59:
	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		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>		<div class="equation"><math>
	F(x)=\sum_{j=0}^{2^n-1}\delta_jx^j~,~~\delta_j\in \Bbb{F}_{2^n}.		F(x)=\sum_{j=0}^{2^n-1}\delta_jx^j~,~~\delta_j\in \Bbb{F}_{2^n}.
	</math></div>		</math></div>

Ivi062 at 11:57, 2 October 2019

2019-10-02T11:57:11Z

← Older revision		Revision as of 11:57, 2 October 2019
Line 70:		Line 70:
	\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).		\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).
	</math></div>		</math></div>

	~~== Equivalence Relations ==~~
	~~Two vectorial Boolean functions <math>F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> are called~~
	* affine (linear) equivalent if there exist <math>A_1,A_2</math> affine (linear) permutations of <math>\mathbb{F}_2^m</math> and <math>\mathbb{F}_2^n</math> respectively, such that <math>F'=A_1\circ F\circ A_2</math>;
	* extended affine equivalent (shortly EA-equivalent) if there exists <math>A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> affine such that <math>F'=F''+A</math>, with <math>F''</math> affine equivalent to <math>F</math>;
	* Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_2^n\times\mathbb{F}_2^m</math> such that the image of the graph of <math>F</math> is the graph of <math>F'</math>, i.e. <math>\mathcal{L}(G_F)=G_{F'}</math> with <math>G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\}</math> and <math>G_{F'}=\{ (x,F'(x)) : x\in\mathbb{F}_2^n\}</math>.

	== Basic Properties of Vectorial Boolean Functions ==		== Basic Properties of Vectorial Boolean Functions ==

Ivi062 at 14:57, 23 September 2019

2019-09-23T14:57:21Z

← Older revision		Revision as of 14:57, 23 September 2019
Line 2:		Line 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.		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>(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>.		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 ==

Ivi062 at 10:21, 5 September 2019

2019-09-05T10:21:36Z

← Older revision		Revision as of 10:21, 5 September 2019
Line 70:		Line 70:
	\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).		\max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).
	</math></div>		</math></div>

			== Equivalence Relations ==
			Two vectorial Boolean functions <math>F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> are called
			* affine (linear) equivalent if there exist <math>A_1,A_2</math> affine (linear) permutations of <math>\mathbb{F}_2^m</math> and <math>\mathbb{F}_2^n</math> respectively, such that <math>F'=A_1\circ F\circ A_2</math>;
			* extended affine equivalent (shortly EA-equivalent) if there exists <math>A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> affine such that <math>F'=F''+A</math>, with <math>F''</math> affine equivalent to <math>F</math>;
			* Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_2^n\times\mathbb{F}_2^m</math> such that the image of the graph of <math>F</math> is the graph of <math>F'</math>, i.e. <math>\mathcal{L}(G_F)=G_{F'}</math> with <math>G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\}</math> and <math>G_{F'}=\{ (x,F'(x)) : x\in\mathbb{F}_2^n\}</math>.

	== Basic Properties of Vectorial Boolean Functions ==		== Basic Properties of Vectorial Boolean Functions ==

Ivi062 at 11:54, 29 August 2019

2019-08-29T11:54:08Z

← Older revision		Revision as of 11:54, 29 August 2019
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 =

Nikolay at 18:24, 10 February 2019

2019-02-10T18:24:07Z

@@ Line 69: / Line 69: @@
 \max_{j=0,\dots ,2^n-1/\, \delta_j\neq 0}w_2(j).
 </math></div>
 == Basic Properties of Vectorial Boolean Functions ==
@@ Line 82: / Line 78: @@
 <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>.

129.177.123.137 at 21:18, 30 December 2018

2018-12-30T21:18:23Z

← Older revision		Revision as of 21:18, 30 December 2018
Line 53:		Line 53:

	and is equal to the maximal algebraic degree of the coordinate functions of <math>F</math>.		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>

			=== Multi-dimensional Walsh Transform ===

			TODO

			== 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>.

			=== Covering Sequences ===

			TODO

			=== Algebraic Immunity ===

			TODO

Nikolay at 21:02, 30 December 2018

2018-12-30T21:02:02Z

← Older revision		Revision as of 21:02, 30 December 2018
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^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.		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,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>.		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^m \rightarrow \mathbb{F}_2^n</math> is the integer-valued function <math>W_F : \mathbb{F}_2^m \times \mathbb{F}_2^n</math> defined by		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^m} (-1)^{v \cdot F(x) + u \cdot x}		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^m \times {\mathbb{F}_2^n}^*</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>.		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>.

Nikolay at 20:33, 30 December 2018

2018-12-30T20:33:57Z

← Older revision		Revision as of 20:33, 30 December 2018
Line 18:		Line 18:
	== Walsh transform ==		== Walsh transform ==

			The <span class="definition">Walsh transform</span> of <math>F : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n</math> is the integer-valued function <math>W_F : \mathbb{F}_2^m \times \mathbb{F}_2^n</math> defined by

			<div class="equation><math>
			W_F(u,v) = \sum_{x \in \mathbb{F}_2^m} (-1)^{v \cdot F(x) + u \cdot x}
			</math></div>

			It can be observed that the Walsh transform of some <math>F</math> is in fact the Fourier transform of the indicator of its graph, i.e. the Fourier transform of the function <math>1_{G_F}</math> defined as
			<div class="equation><math>
			1_{G_F}(x,y) = \begin{cases}
			1 & F(x) = y \\
			0 & F(x) \ne y.
			\end{cases}
			</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^m \times {\mathbb{F}_2^n}^*</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 ==

Nikolay at 20:26, 30 December 2018

2018-12-30T20:26:19Z

← Older revision		Revision as of 20:26, 30 December 2018
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 =