Plateaued Functions

Background and Definition

A Boolean function $f:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2}$ is said to be plateaued if its Walsh transform takes at most three distinct values, viz. $0$ and $\pm \mu$ for some positive ineger $\mu$ called the amplitude of $f$.

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if $F$ is an $(n,m)$-function, we say that $F$ is plateaued if all its component functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\cdot F} for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\neq 0} are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that $F$ is plateaued with single amplitude.

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

The Maiorana-MacFarland class of bent functions can be generalized into the class of functions $f_{\phi ,h}$ of the form

$f_{\phi ,h}(x,y)=x\cdot \phi (y)+h(y)$

for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\in \mathbb {F} _{2}^{r},y\in \mathbb {F} _{2}^{s}} , where $r$ and $s$ are any positive integers, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=r+s} , $\phi :\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}^{r}$ is arbitrary and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle h:\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}} is any Boolean function.

The Walsh transform of $f_{\phi ,h}$ takes the value

$W_{f_{\phi ,h}}(a,b)=2^{r}\sum _{y\in \phi ^{-1}(a)}(-1)^{b\cdot y+h(y)}$

at Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,b)} . If $\phi$ is injective, resp. takes each value in its image set two times, then $f_{\phi ,h}$ is plateaued of amplitude Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{r}} , resp. Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{r+1}} .

Characterization of Plateaued Functions

Characterization by the Derivatives

Using the fact that a Boolean function $f$ is plateaued if and only if the expression $\sum _{a,b\in \mathbb {F} _{2}^{n}}(-1)^{DaDbf(x)}$ does not depend on $x\in \mathbb {F} _{2}^{n}$, one can derive the following characterization.

Let $F$ be an $(n,m)$-function. Then:

• F is plateuaed if and only if, for every $v\in \mathbb {F} _{2}^{m}$, the size of the set

$\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}$

does not depend on $x$;

• F is plateaued with single amplitude if and only if the size of the set depends neither on $x$, nor on $v\in \mathbb {F} _{2}^{m}$ for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\neq 0} .

Moreover:

• for every $F$, the value distribution of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D_{a}D_{b}F(x)} equals that of $D_{a}F(b)+D_{a}F(x)$ when Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,b)} ranges over Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\mathbb {F} _{2}^{n})^{2}} ;

• if two plateaued functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F,G} have the same distribution, then all of their component functions $u\cdot F,u\cdot G$ have the same amplitude.

Power Functions

Let $F(x)=x^{d}$. Then, for every $v,x,\lambda \in \mathbb{F}_{2^n}</math> with $\lambda \neq 0$, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(x)=v\}|=|\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(x/\lambda )=v/\lambda ^{d}\}|.}

Then:

• $F$ is plateaued if and only if, for every $v\in \mathbb {F} _{2^{n}}$, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(1)=v\}|=|\{(a,b)\in \mathbb {F} _{2^{n}}^{2}:D_{a}F(b)+D_{a}F(0)=v\}|;}

• $F$ is plateaued with single amplitude if and only if the size above does not, in addition, depend on $v\neq 0$.

Functions with Unbalanced Components

Let $F$ be an $(n,m)$-function. Then $F$ is plateuaed with all components unbalanced if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v,x\in \mathbb {F} _{2}^{n}} , we have

$|\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}|=|\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:F(a)+F(b)=v\}|.$

Moreover, $F$ is plateaued with single amplitude if and only if this value does not, in addition, depend on $v$ for $v\neq 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 ${\rm {Im}}(D_{a}F)$ of any derivative of a strongly-plateaued function $F$ is an affine space.

Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean function $f$ is defined as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\Delta _{f}}(a)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{f(x)+f(x+a)}} .

An $n$-variable Boolean function $f$ is plateaued if and only if, for every $x\in \mathbb {F} _{2}^{n}$, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $(n,m)$-function $F$ is plateaued if and only if, for every $x\in \mathbb {F} _{2}^{n},u\in \mathbb {F} _{2}^{m}$, we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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, $F$ is plateaued with single amplitude if and only if, for every $x\in \mathbb {F} _{2}^{n},u\in \mathbb {F} _{2}^{m}$, we have

$\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, $F$ is plateuaed if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x,v\in \mathbb {F} _{2}^{n}} , we have

$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 $f:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2}$ is plateuaed if and only if, for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0\neq \alpha \in \mathbb {F} _{2}^{n}} , we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{w\in \mathbb {F} _{2}^{n}}W_{f}(w+\alpha )W_{f}^{3}(w)=0.}

An $(n,m)$-function $F$ is plateuaed if and only if for every Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\in \mathbb {F} _{2}^{m}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0\neq \alpha \in \mathbb {F} _{2}^{n}} , we have

$\sum _{w\in \mathbb {F} _{2}^{n}}W_{F}(w+\alpha ,u)W_{F}^{3}(w,u)=0.$

Furthermore, $F$ is plateaued with single amplitude if and only if, in addition, the sum Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{w\in \mathbb {F} _{2}^{n}}W_{F}^{4}(w,u)} does not depend on $u$ for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\neq 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 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b\in \mathbb {F} _{2}} , we have

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $(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.

Characterization of APN among Plateaued Functions

Characterization by the Derivatives

One very useful property of quadratic functions which extends to plateaued functions is that it suffices to consider the number of solutions to the differential equation 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(x) = D_aF(0)} in order to decided the APN-ness of a given 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} . More precisely, a plateuaed 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 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 APN if and only if the equation

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) + F(x+a) = F(0) + F(a)}

has at most two solutions for 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 0 \ne a \in \mathbb{F}_2^n} .

Characterization by the Walsh Transform

Suppose 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 a plateaued 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 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 F(0) = 0} . 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 APN 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 | \{ (x,b) \in \mathbb{F}_{2^n}^2 : F(x) + F(x+b) + F(b) = 0 \} | = 3 \cdot 2^n - 2,}

or, equivalently,

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}, u \in \mathbb{F}_{2^n}^*} W_F^3(a,u) = 2^{2n+1}(2^n-1).}

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 satisfies the inequality

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 3 \cdot 2^{3^n} - 2^{2n + 1} \le \sum_{u \in \mathbb{F}_2^n} \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 APN plateaued.

If we denote by 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^{\lambda_u}} the amplitude of the component 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 u \cdot F} of a given plateuaed 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} , 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 APN if and only if <div><math>\sum_{0 \ne u \in \mathbb{F}_2^n} 2^{2 \lambda_u} \le 2^{n+1}(2^n-1).}

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,n)} -plateaued function with all components unbalanced. 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 | \{ (a,b) \in (\mathbb{F}_2^n)^2 : a \ne b, F(a) = F(b)\}| \ge 2 \cdot (2^n-1),}

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