Background and Definition

A Boolean function ${\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. ${\displaystyle 0}$ and ${\displaystyle \pm \mu }$ for some positive ineger ${\displaystyle \mu }$ called the amplitude of ${\displaystyle f}$.

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if ${\displaystyle F}$ is an ${\displaystyle (n,m)}$-function, we say that ${\displaystyle F}$ is plateaued if all its component functions ${\displaystyle u\cdot F}$ for ${\displaystyle u\neq 0}$ are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that ${\displaystyle 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 [1]

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

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

for ${\displaystyle x\in \mathbb {F} _{2}^{r},y\in \mathbb {F} _{2}^{s}}$, where ${\displaystyle r}$ and ${\displaystyle s}$ are any positive integers, ${\displaystyle n=r+s}$, ${\displaystyle \phi :\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}^{r}}$ is arbitrary and ${\displaystyle h:\mathbb {F} _{2}^{s}\rightarrow \mathbb {F} _{2}}$ is any Boolean function.

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

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

at ${\displaystyle (a,b)}$. If ${\displaystyle \phi }$ is injective, resp. takes each value in its image set two times, then ${\displaystyle f_{\phi ,h}}$ is plateaued of amplitude ${\displaystyle 2^{r}}$, resp. ${\displaystyle 2^{r+1}}$.

Characterization of Plateaued Functions [2]

Characterization by the Derivatives

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

Let ${\displaystyle F}$ be an ${\displaystyle (n,m)}$-function. Then:

• F is plateuaed if and only if, for every ${\displaystyle v\in \mathbb {F} _{2}^{m}}$, the size of the set
${\displaystyle \{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:D_{a}D_{b}F(x)=v\}}$

does not depend on ${\displaystyle x}$;

• F is plateaued with single amplitude if and only if the size of the set depends neither on ${\displaystyle x}$, nor on ${\displaystyle v\in \mathbb {F} _{2}^{m}}$ for ${\displaystyle v\neq 0}$.

Moreover:

• for every ${\displaystyle F}$, the value distribution of ${\displaystyle D_{a}D_{b}F(x)}$ equals that of ${\displaystyle D_{a}F(b)+D_{a}F(x)}$ when ${\displaystyle (a,b)}$ ranges over ${\displaystyle (\mathbb {F} _{2}^{n})^{2}}$;
• if two plateaued functions ${\displaystyle F,G}$ have the same distribution, then all of their component functions ${\displaystyle u\cdot F,u\cdot G}$ have the same amplitude.

Power Functions

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

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

• ${\displaystyle F}$ is plateaued if and only if, for every ${\displaystyle v\in \mathbb {F} _{2^{n}}}$, we have
${\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\}|;}$
• ${\displaystyle F}$ is plateaued with single amplitude if and only if the size above does not, in addition, depend on ${\displaystyle v\neq 0}$.

Functions with Unbalanced Components

Let ${\displaystyle F}$ be an ${\displaystyle (n,m)}$-function. Then ${\displaystyle F}$ is plateuaed with all components unbalanced if and only if, for every ${\displaystyle v,x\in \mathbb {F} _{2}^{n}}$, we have

${\displaystyle |\{(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, ${\displaystyle F}$ is plateaued with single amplitude if and only if this value does not, in addition, depend on ${\displaystyle v}$ for ${\displaystyle v\neq 0}$.

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.