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 $u\cdot F$ for $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 $x\in \mathbb {F} _{2}^{r},y\in \mathbb {F} _{2}^{s}$, where $r$ and $s$ are any positive integers, $n=r+s$, $\phi :\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}^{r}$ is arbitrary and $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 $(a,b)$. If $\phi$ is injective, resp. takes each value in its image set two times, then $f_{\phi ,h}$ is plateaued of amplitude $2^{r}$, resp. $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 $v\neq 0$.

Moreover:

• for every $F$, the value distribution of $D_{a}D_{b}F(x)$ equals that of $D_{a}F(b)+D_{a}F(x)$ when $(a,b)$ ranges over $(\mathbb {F} _{2}^{n})^{2}$;

• if two plateaued functions $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

$|\{(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

$|\{(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 $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 ${\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

$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

$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 $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 $0\neq \alpha \in \mathbb {F} _{2}^{n}$, we have

$\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 $u\in \mathbb {F} _{2}^{m}$ and $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 $\sum _{w\in \mathbb {F} _{2}^{n}}W_{F}^{4}(w,u)$ does not depend on $u$ for $u\neq 0$.

Second Characterization

A Boolean function $f:\mathbb {F} _{2^{n}}\rightarrow \mathbb {F} _{2}$ is plateuaed if and only if, for every $b\in \mathbb {F} _{2}$, we have

$\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 $F$ is plateuaed if and only if, for every $b\in \mathbb {F} _{2}^{n}$ and every $u\in \mathbb {F} _{m}$, we have

$\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, $F$ is plateaued with single amplitude if and only if the two sums above do not depend on $u$ for $u\neq 0$.

Third Characterization

Any Boolean function $f$ in $n$ variables satisfies

$\left(\sum _{a\in \mathbb {F} _{2}^{n}}W_{f}^{4}(a)\right)^{2}\leq 2^{2n}\left(\sum _{a\in \mathbb {F} _{2}^{n}}W_{f}^{6}(a)\right),$

with equality if and only if $f$ is plateuaed.

Any $(n,m)$-function $F$ satisfies

$\sum _{u\in \mathbb {F} _{2}^{m}}\left(\sum _{a\in \mathbb {F} _{2}^{n}}W_{F}^{4}(a,u)\right)^{2}\leq 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 $F$ is plateuaed.

In addition, every $(n,m)$-function satisfies

$\sum _{u\in \mathbb {F} _{2}^{m}}\sum _{a\in \mathbb {F} _{2}^{n}}W_{F}^{4}(a,u)\leq 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 $F$ is plateuaed.