Boolean Functions - Revision history

Ivi062: /* The Nonlinearity */

2019-10-25T14:39:22Z

The Nonlinearity

← Older revision		Revision as of 14:39, 25 October 2019
Line 112:		Line 112:
	* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}\|W_f(u)\|</math>.		* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}\|W_f(u)\|</math>.
	* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.		* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.
	* A function achieving the covering radius bound with equality is called ~~<em>~~bent~~</em>~~ (𝑛 is an even integer and the function is not balanced).		* A function achieving the covering radius bound with equality is called [[Bent Boolean Functions\| bent]] (𝑛 is an even integer and the function is not balanced).
	* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.		* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.
	* 𝑓 is bent if and only if for any nonzero element 𝑎 the Boolean function 𝐷<sub>𝑎</sub>𝑓(𝑥)=𝑓(𝑥+𝑎)+𝑓(𝑥) is balanced.		* 𝑓 is bent if and only if for any nonzero element 𝑎 the Boolean function 𝐷<sub>𝑎</sub>𝑓(𝑥)=𝑓(𝑥+𝑎)+𝑓(𝑥) is balanced.

Ivi062: /* The Nonlinearity */

2019-10-14T14:15:34Z

The Nonlinearity

← Older revision		Revision as of 14:15, 14 October 2019
Line 114:		Line 114:
	* A function achieving the covering radius bound with equality is called <em>bent</em> (𝑛 is an even integer and the function is not balanced).		* A function achieving the covering radius bound with equality is called <em>bent</em> (𝑛 is an even integer and the function is not balanced).
	* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.		* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.
			* 𝑓 is bent if and only if for any nonzero element 𝑎 the Boolean function 𝐷<sub>𝑎</sub>𝑓(𝑥)=𝑓(𝑥+𝑎)+𝑓(𝑥) is balanced.

	==Correlation-immunity order==		==Correlation-immunity order==

Ivi062: /* Correlation-immunity order */

2019-10-11T15:52:00Z

Correlation-immunity order

← Older revision		Revision as of 15:52, 11 October 2019
Line 119:		Line 119:
	Balanced 𝑚-th order correlation-immune functions are called <em>𝑚-resilient</em>.		Balanced 𝑚-th order correlation-immune functions are called <em>𝑚-resilient</em>.

	Given 𝑓 a 𝑛-variable function with correlation-immunity of order 𝑚 then <center>𝑛+𝑑°𝑓≤𝑛.</center>		Given 𝑓 a 𝑛-variable function with correlation-immunity of order 𝑚 then <center>𝑚+𝑑°𝑓≤𝑛.</center>
	If 𝑓 is also balanced, then <center>𝑛+𝑑°𝑓≤𝑛-1.</center>		If 𝑓 is also balanced, then <center>𝑚+𝑑°𝑓≤𝑛-1.</center>

Ivi062 at 15:51, 11 October 2019

2019-10-11T15:51:19Z

← Older revision		Revision as of 15:51, 11 October 2019
Line 99:		Line 99:
	* If 𝑓,𝑔 are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.		* If 𝑓,𝑔 are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.

	=The Nonlinearity=		=Properties important for cryptographic applications=

			==Balanced functions==
			An 𝑛-variable Boolean function 𝑓 is called <em>balanced</em> if 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>, so its output is uniformly distributed.
			Such functions cannot have maximal degree.
			Most cryptographic applications use balanced Boolean functions.

			==The Nonlinearity==
	The <em>nonlinearity</em> of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called 𝒜 the set of all affine 𝑛-variable functions,		The <em>nonlinearity</em> of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called 𝒜 the set of all affine 𝑛-variable functions,
	<center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center>		<center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center>
Line 105:		Line 112:
	* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}\|W_f(u)\|</math>.		* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}\|W_f(u)\|</math>.
	* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.		* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.
	* A function achieving the covering radius bound with equality is called <em>bent</em> (𝑛 is an even integer).		* A function achieving the covering radius bound with equality is called <em>bent</em> (𝑛 is an even integer and the function is not balanced).
	* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.		* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.

			==Correlation-immunity order==
			A Boolean function 𝑓 is <em>𝑚-th order correlation-immune</em> if the probability distribution of the output is unaltered when any 𝑚 input variables are fixed.
			Balanced 𝑚-th order correlation-immune functions are called <em>𝑚-resilient</em>.

			Given 𝑓 a 𝑛-variable function with correlation-immunity of order 𝑚 then <center>𝑛+𝑑°𝑓≤𝑛.</center>
			If 𝑓 is also balanced, then <center>𝑛+𝑑°𝑓≤𝑛-1.</center>

Ivi062 at 15:34, 11 October 2019

2019-10-11T15:34:09Z

← Older revision		Revision as of 15:34, 11 October 2019
Line 77:		Line 77:
	* If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌<sub>𝐻</sub>(𝑓)≥2<sup>𝑛-𝑟</sup>.		* If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌<sub>𝐻</sub>(𝑓)≥2<sup>𝑛-𝑟</sup>.
	* 𝓌<sub>𝐻</sub>(𝑓) is odd if and only if 𝑑°𝑓=𝑛.		* 𝓌<sub>𝐻</sub>(𝑓) is odd if and only if 𝑑°𝑓=𝑛.


	=The Walsh transform=		=The Walsh transform=
Line 98:		Line 97:

	* The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.		* The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
	* If 𝑓,𝑔 are affine equivalent, then		* If 𝑓,𝑔 are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.

	=The Nonlinearity=		=The Nonlinearity=

Ivi062: /* Equivalences of Boolean functions */

2019-10-11T15:28:47Z

Equivalences of Boolean functions

← Older revision		Revision as of 15:28, 11 October 2019
Line 95:		Line 95:

	Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>		Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>
	A parameter that is preserved by ~~EA-~~equivalence is called <i>~~EA-~~invariant</i>.		A parameter that is preserved by an equivalence relation is called <i>invariant</i>.

			* The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
			* If 𝑓,𝑔 are affine equivalent, then

	=The Nonlinearity=		=The Nonlinearity=

Ivi062: /* Equivalence of Boolean functions */

2019-10-11T15:24:17Z

Equivalence of Boolean functions

← Older revision		Revision as of 15:24, 11 October 2019
Line 91:		Line 91:
	* Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements 𝑎,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = \|E^\perp\|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center> for 𝐸<sup>⟂</sup> the orthogonal subspace of 𝐸,{𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> : 𝑢·𝑥=0, for all 𝑥∈𝐸}.		* Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements 𝑎,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = \|E^\perp\|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center> for 𝐸<sup>⟂</sup> the orthogonal subspace of 𝐸,{𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> : 𝑢·𝑥=0, for all 𝑥∈𝐸}.

	=~~Equivalence~~ of Boolean functions=		=Equivalences of Boolean functions=
			Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>affine equivalent</i> if there exists a linear automorphism 𝐿 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎).</center>

	Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>		Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>
	A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>.		A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>.

Ivi062 at 15:20, 11 October 2019

2019-10-11T15:20:44Z

← Older revision		Revision as of 15:20, 11 October 2019
Line 70:		Line 70:

	When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n \| A_j\ne0}w_2(j)</math>, where 𝓌<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗.		When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n \| A_j\ne0}w_2(j)</math>, where 𝓌<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗.

			=On the weight of a Boolean function=
			For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied.
			* If 𝑑°𝑓=1 then 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>.
			* If 𝑑°𝑓=2 then 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup> or 𝓌<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>±2<sup>𝑛-1-ℎ</sup>, with 0≤ℎ≤𝑛/2.
			* If 𝑑°𝑓≤𝑟 and 𝑓 nonzero then 𝓌<sub>𝐻</sub>(𝑓)≥2<sup>𝑛-𝑟</sup>.
			* 𝓌<sub>𝐻</sub>(𝑓) is odd if and only if 𝑑°𝑓=𝑛.


	=The Walsh transform=		=The Walsh transform=

Ivi062 at 08:43, 2 October 2019

2019-10-02T08:43:44Z

← Older revision		Revision as of 08:43, 2 October 2019
Line 8:		Line 8:
	The Hamming weight of 𝑥 is the size of its support (<math>w_H(x)=\|supp_x\|</math>).		The Hamming weight of 𝑥 is the size of its support (<math>w_H(x)=\|supp_x\|</math>).
	Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.		Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.
	The Hamming distance of two functions 𝑓,𝑔 is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.		The Hamming distance of two functions 𝑓,𝑔 (𝖽<sub>𝐻</sub>(𝑓,𝑔)) is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.

	=Representation of a Boolean function=		=Representation of a Boolean function=
Line 75:		Line 75:
	With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> 𝑥·𝑦, the value of 𝑊<sub>𝑓</sub> at 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers)		With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> 𝑥·𝑦, the value of 𝑊<sub>𝑓</sub> at 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers)
	<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center>		<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center>
	The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}</math> is the <i>Walsh support</i> of 𝑓.		The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}=\{ u\in\mathbb{F}_2^n : W_f(u)=1 \}</math> is the <i>Walsh support</i> of 𝑓.

	==Properties of the Walsh transform==		==Properties of the Walsh transform==
Line 86:		Line 86:
	Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>		Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor 𝑎 such that <center>𝑔(𝑥) = 𝑓(𝐿(𝑥)+𝑎)+𝓁(𝑥).</center>
	A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>.		A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>.

			=The Nonlinearity=
			The <em>nonlinearity</em> of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called 𝒜 the set of all affine 𝑛-variable functions,
			<center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center>

			* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}\|W_f(u)\|</math>.
			* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.
			* A function achieving the covering radius bound with equality is called <em>bent</em> (𝑛 is an even integer).
			* 𝑓 is bent if and only if 𝑊<sub>𝑓</sub>(𝑢)=±2<sup>𝑛/2</sup>, for every 𝑢∈𝔽<sub>2</sub><sup>𝑛</sup>.

Ivi062: /* Trace representation */

2019-10-02T08:16:16Z

Trace representation

← Older revision		Revision as of 08:16, 2 October 2019
Line 68:		Line 68:

	𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math> where 𝘗 is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>≠0.		𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math> where 𝘗 is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>≠0.

			When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n \| A_j\ne0}w_2(j)</math>, where 𝓌<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗.

	=The Walsh transform=		=The Walsh transform=