# Plateaued Functions

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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. 0 and ±𝜇 for some positive ineger 𝜇 called the amplitude of 𝑓.

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if 𝐹 is an (𝑛,𝑚)-function, we say that 𝐹 is plateaued if all its component functions 𝑢⋅𝐹 for 𝑢≠0 are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that 𝐹 is plateaued with single amplitude.

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

## 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 𝑟 and 𝑠 are any positive integers, 𝑛 = 𝑟 + 𝑠, ${\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 (𝑎,𝑏). If 𝜑 is injective, resp. takes each value in its image set two times, then ${\displaystyle f_{\phi ,h}}$ is plateaued of amplitude 2𝑟, resp. 2𝑟+1.

# Characterization of Plateaued Functions [2]

## Characterization by the Derivatives

Using the fact that a Boolean function 𝑓 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 𝐹 be an (𝑛,𝑚)-function. Then:

• 𝐹 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}$;

• 𝐹 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 𝐹, 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 𝐹,𝐺 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:

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

## Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean function ${\displaystyle f}$ is defined as ${\displaystyle {\Delta _{f}}(a)=\sum _{x\in \mathbb {F} _{2}^{n}}(-1)^{f(x)+f(x+a)}}$.

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

${\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 (𝑛,𝑚)-function 𝐹 is plateaued if and only if, for every ${\displaystyle x\in \mathbb {F} _{2}^{n},u\in \mathbb {F} _{2}^{m}}$, we have

${\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, 𝐹 is plateaued with single amplitude if and only if, for every ${\displaystyle x\in \mathbb {F} _{2}^{n},u\in \mathbb {F} _{2}^{m}}$, we have

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

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

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

An (𝑛,𝑚)-function 𝐹 is plateuaed if and only if for every ${\displaystyle u\in \mathbb {F} _{2}^{m}}$ and ${\displaystyle 0\neq \alpha \in \mathbb {F} _{2}^{n}}$, we have

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

Furthermore, 𝐹 is plateaued with single amplitude if and only if, in addition, the sum ${\displaystyle \sum _{w\in \mathbb {F} _{2}^{n}}W_{F}^{4}(w,u)}$ does not depend on ${\displaystyle u}$ for ${\displaystyle u\neq 0}$.

### Second Characterization

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

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

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

### Third Characterization

Any Boolean function 𝑓 in ${\displaystyle n}$ variables satisfies

${\displaystyle \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 𝑓 is plateuaed.

Any (𝑛,𝑚)-function 𝐹 satisfies

${\displaystyle \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 𝐹 is plateuaed.

${\displaystyle \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 𝐹 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 ${\displaystyle D_{a}F(x)=D_{a}F(0)}$ in order to decided the APN-ness of a given function 𝐹. More precisely, a plateuaed (𝑛,𝑛) function 𝐹 is APN if and only if the equation

${\displaystyle F(x)+F(x+a)=F(0)+F(a)}$

has at most two solutions for any ${\displaystyle 0\neq a\in \mathbb {F} _{2}^{n}}$.

## Characterization by the Walsh Transform

Suppose 𝐹 is a plateaued (𝑛,𝑛) function with ${\displaystyle F(0)=0}$. Then 𝐹 is APN if and only if

${\displaystyle |\{(x,b)\in \mathbb {F} _{2^{n}}^{2}:F(x)+F(x+b)+F(b)=0\}|=3\cdot 2^{n}-2,}$

or, equivalently,

${\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 (𝑛,𝑛)-function satisfies the inequality

${\displaystyle 3\cdot 2^{3^{n}}-2^{2n+1}\leq \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 𝐹 is APN plateaued.

If we denote by ${\displaystyle 2^{\lambda _{u}}}$ the amplitude of the component function ${\displaystyle u\cdot F}$ of a given plateuaed function ${\displaystyle F}$, then 𝐹 is APN if and only if

${\displaystyle \sum _{0\neq u\in \mathbb {F} _{2}^{n}}2^{2\lambda _{u}}\leq 2^{n+1}(2^{n}-1).}$

## Functions with Unbalanced Components

Let 𝐹 be an (𝑛,𝑛)-plateaued function with all components unbalanced. Then

${\displaystyle |\{(a,b)\in (\mathbb {F} _{2}^{n})^{2}:a\neq b,F(a)=F(b)\}|\geq 2\cdot (2^{n}-1),}$

with equality if and only if 𝐹 is APN.

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.