Plateaued Functions: Difference between revisions

From Boolean
No edit summary
No edit summary
Line 106: Line 106:


<div><math> 2^n | \{ (a,b,c) \in (\mathbb{F}_2^n)^3 : F(a) + F(b) + F(c) + F(a+b+c+x) = v \}| = | \{ (a,b,c,d) \in (\mathbb{F}_2^n)^4 : F(a) + F(b) + F(c) + F(a+b+c) + F(d) + F(d+x) = v \}|.</math></div>
<div><math> 2^n | \{ (a,b,c) \in (\mathbb{F}_2^n)^3 : F(a) + F(b) + F(c) + F(a+b+c+x) = v \}| = | \{ (a,b,c,d) \in (\mathbb{F}_2^n)^4 : F(a) + F(b) + F(c) + F(a+b+c) + F(d) + F(d+x) = v \}|.</math></div>
== Characterization by the Means of the Power Moments of the Walsh Transform ==
=== First Characterization ===
A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is plateuaed if and only if, for every <math>0 \ne \alpha \in \mathbb{F}_2^n</math>, we have
<div><math>\sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0.</math></div>
An <math>(n,m)</math>-function <math>F</math> is plateuaed if and only if for every <math>u \in \mathbb{F}_2^m</math> and <math>0 \ne \alpha \in \mathbb{F}_2^n</math>, we have
<div><math>\sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0.</math></div>
Furthermore, <math>F</math> is plateaued with single amplitude if and only if, in addition, the sum <math>\sum_{w \in \mathbb{F}_2^n} W_F^4(w,u)</math> does not depend on <math>u</math> for <math>u \ne 0</math>.
=== Second Characterization ===
A Boolean function <math>f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2</math> is plateuaed if and only if, for every <math>b \in \mathbb{F}_2</math>, we have
<div><math> \sum_{a \in \mathbb{F}_2} W_f^4(a) = 2^n(-1)^{f(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_f^3(a). </math></div>
An <math>(n,m)</math>-function <math>F</math> is plateuaed if and only if, for every <math>b \in \mathbb{F}_2^n</math> and every <math>u \in \mathbb{F}_m</math>, we have
<div><math> \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) = 2^n(-1)^{u \cdot F(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_F^3(a,u).</math></div>
Moreover, <math>F</math> is plateaued with single amplitude if and only if the two sums above do not depend on <math>u</math> for <math>u \ne 0</math>.
=== Third Characterization ===
Any Boolean function <math>f</math> in <math>n</math> variables satisfies
<div><math> \left( \sum_{a \in \mathbb{F}_2^n} W_f^4(a) \right)^2 \le 2^{2n} \left( \sum_{a \in \mathbb{F}_2^n} W_f^6(a) \right), </math></div>
with equality if and only if <math>f</math> is plateuaed.
Any <math>(n,m)</math>-function <math>F</math> satisfies
<div><math> \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \right)^2 \le 2^{2n} \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) \right), </math></div>
with equality if and only if <math>F</math> is plateuaed.
In addition, every <math>(n,m)</math>-function satisfies
<div><math>\sum_{u \in \mathbb{F}_2^m} \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \le 2^n \sum_{u \in \mathbb{F}_2^m} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) }, </math></div>
with equality if and only if <math>F</math> is plateuaed.

Revision as of 15:28, 8 February 2019

Background and Definition

A Boolean function is said to be plateaued if its Walsh transform takes at most three distinct values, viz. Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0} and 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 \pm \mu} for some positive ineger 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 \mu} called the amplitude 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} .

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, 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 F} is 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, we say that 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 plateaued if all its component 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 u \cdot F} 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 u \ne 0} are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that 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 plateaued with single amplitude.

The characterization by means of the derivatives below suggests the following definition: a v.B.f. 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 said to be strongly-plateuaed if, for every 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} and every 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} , the size of the set 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 \{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}} does not depend on 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 x} , or, equivalently, the size of the set 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 \{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}} does not depend on 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 x} .

Equivalence relations

The class of functions that are plateaued with single amplitude is CCZ-invariant.

The class of plateaued functions is only EA-invariant.

Relations to other classes of functions

All bent and semi-bent Boolean functions are plateaued.

Any vectorial AB function is plateaued with single amplitude.

Constructions of Boolean plateaued functions

Primary constructons

Generalization of the Maiorana-MacFarland Functions [1]

The Maiorana-MacFarland class of bent functions can be generalized into the class of 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_{\phi,h}} of the form

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_{\phi,h}(x,y) = x \cdot \phi(y) + h(y)}

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 x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s} , 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 r} and 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 s} are any positive integers, 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 = r + s} , 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 \phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r} is arbitrary and 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 h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2} is any Boolean function.

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_{\phi,h}} takes the value

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_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)}}

at 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,b)} . 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 \phi} is injective, resp. takes each value in its image set two times, then 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_{\phi,h}} is plateaued of amplitude 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^r} , resp. 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^{r+1}} .

Characterization of Plateaued Functions [2]

Characterization by the Derivatives

Using the fact that a Boolean 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 plateaued if and only if the expression 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 \sum_{a,b \in \mathbb{F}_2^n} (-1)^{DaDbf(x)}} does not depend on 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 x \in \mathbb{F}_2^n} , one can derive the following characterization.

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 F} be 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. Then:

  • F is plateuaed if and only if, for every 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 \in \mathbb{F}_2^m} , the size of the set
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,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}}

does not depend on 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 x} ;

  • F is plateaued with single amplitude if and only if the size of the set depends neither on 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 x} , nor on 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 \in \mathbb{F}_2^m} 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 v \ne 0} .

Moreover:

  • for every 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 value distribution 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 D_aD_bF(x)} equals that 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 D_aF(b) + D_aF(x)} when 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,b)} ranges 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)^2} ;
  • if two plateaued 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,G} have the same distribution, then all of their component 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 u \cdot F, u\cdot G} have the same amplitude.

Power Functions

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 F(x) = x^d} . Then, for every $v,x,\lambda \in \mathbb{F}_{2^n}</math> 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 \lambda \ne 0} , we have

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,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(x) = v \} | = | \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(x/\lambda) = v/\lambda^d \}|.}

Then:

  • 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 plateaued if and only if, for every 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 \in \mathbb{F}_{2^n}} , we have
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,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(1) = v \} | = | \{ (a,b) \in \mathbb{F}_{2^n}^2 : D_aF(b) + D_aF(0) = v \}|;}
  • 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 plateaued with single amplitude if and only if the size above does not, in addition, depend on 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 \ne 0} .

Functions with Unbalanced Components

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 F} be 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. Then 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 plateuaed with all components unbalanced if and only if, for every 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,x \in \mathbb{F}_{2}^n} , we have

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,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}| = | \{ (a,b) \in (\mathbb{F}_2^n)^2 : F(a) + F(b) = v \}|.}

Moreover, 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 plateaued with single amplitude if and only if this value does not, in addition, depend on 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} 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 v \ne 0} .

Strongly-Plateaued Functions

A Boolean function is strongly-plateaued if and only if its partially-bent. A v.B.f. is strongly-plateaued if and only if all of its component functions are partially-bent. In particular, bent and quadratic Boolean and vectorial functions are strongly-plateaued.

The image set 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 {\rm Im}(D_aF)} of any derivative of a strongly-plateaued 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 an affine space.

Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean 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 defined as 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 {\Delta_f}(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + f(x+a)}} .

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} -variable Boolean 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 plateaued if and only if, for every , we have

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 \sum_{a \in \mathbb{F}_2^n} \Delta_f(a) \Delta_f(a+x) = \left( \sum_{a \in \mathbb{F}_2^n} \Delta_f^2(a) \right) \Delta_f(x).}

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 plateaued if and only if, for every 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 x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m} , we have

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 \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}(a) \Delta_{u \cdot F}(a+x) = \left( \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}^2(a) \right) \Delta_{u \cdot F}(x).}

Furthermore, 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 plateaued with single amplitude if and only if, for every 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 x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m} , we have

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 \sum_{a \in \mathbb{F}_2^n} \Delta_{u \cdot F}(a) \Delta_{u \cdot F}(a+x) = \mu^2 \Delta_{u \cdot F}(x).}

Alternatively, 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 plateuaed if and only if, for every 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 x,v \in \mathbb{F}_2^n} , we have

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 | \{ (a,b,c) \in (\mathbb{F}_2^n)^3 : F(a) + F(b) + F(c) + F(a+b+c+x) = v \}| = | \{ (a,b,c,d) \in (\mathbb{F}_2^n)^4 : F(a) + F(b) + F(c) + F(a+b+c) + F(d) + F(d+x) = v \}|.}

Characterization by the Means of the Power Moments of the Walsh Transform

First Characterization

A Boolean 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 : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2} is plateuaed if and only if, for every 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 0 \ne \alpha \in \mathbb{F}_2^n} , we have

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 \sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0.}

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 plateuaed if and only if for every 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 \in \mathbb{F}_2^m} and 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 0 \ne \alpha \in \mathbb{F}_2^n} , we have

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 \sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0.}

Furthermore, 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 plateaued with single amplitude if and only if, in addition, the sum 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 \sum_{w \in \mathbb{F}_2^n} W_F^4(w,u)} does not depend on 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} 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 u \ne 0} .

Second Characterization

A Boolean 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 : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2} is plateuaed if and only if, for every 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 b \in \mathbb{F}_2} , we have

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 \sum_{a \in \mathbb{F}_2} W_f^4(a) = 2^n(-1)^{f(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_f^3(a). }

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 plateuaed if and only if, for every 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 b \in \mathbb{F}_2^n} and every 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 \in \mathbb{F}_m} , we have

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 \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) = 2^n(-1)^{u \cdot F(b)} \sum_{a \in \mathbb{F}_2^n} (-1)^{a \cdot b} W_F^3(a,u).}

Moreover, 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 plateaued with single amplitude if and only if the two sums above do not depend on 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} 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 u \ne 0} .

Third Characterization

Any Boolean 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} 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 n} variables satisfies

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 \left( \sum_{a \in \mathbb{F}_2^n} W_f^4(a) \right)^2 \le 2^{2n} \left( \sum_{a \in \mathbb{F}_2^n} W_f^6(a) \right), }

with equality 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 f} is plateuaed.

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} satisfies

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 \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \right)^2 \le 2^{2n} \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) \right), }

with equality 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 F} is plateuaed.

In addition, every 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 satisfies

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 \sum_{u \in \mathbb{F}_2^m} \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \le 2^n \sum_{u \in \mathbb{F}_2^m} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) }, }

with equality 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 F} is plateuaed.

  1. ↑ Camion P, Carlet C, Charpin P, Sendrier N. On Correlation-immune functions. InAdvances in Cryptology—CRYPTO’91 1992 (pp. 86-100). Springer Berlin/Heidelberg.
  2. ↑ Carlet C. Boolean and vectorial plateaued functions and APN functions. IEEE Transactions on Information Theory. 2015 Nov;61(11):6272-89.
Retrieved from "http://boolean.wiki.uib.no/index.php?title=Plateaued_Functions&oldid=170"