Plateaued Functions

Background and Definition

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

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