Plateaued Functions

Background and Definition

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

This notion can be naturally extended to vectorial Boolean functions by applying it to each component. More precisely, if <math>F</math> is an <math>(n,m)</math>-function, we say that <math>F</math> is plateaued if all its component functions <math>u \cdot F</math> for <math>u \ne 0</math> are plateaued. If all of the component functions are plateaued and have the same amplitude, we say that <math>F</math> is plateaued with single amplitude.

The characterization by means of the derivatives below suggests the following definition: a v.B.f. <math>F</math> is said to be strongly-plateuaed if, for every <math>a</math> and every <math>v</math>, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aD_bF(x) = v \}</math> does not depend on <math>x</math>, or, equivalently, the size of the set <math>\{ b \in \mathbb{F}_2^n : D_aF(b) = D_aF(x) + v \}</math> does not depend on <math>x</math>.

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 <math>f_{\phi,h}</math> of the form

<math>f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y)</math>

for <math>x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s</math>, where <math>r</math> and <math>s</math> are any positive integers, <math>n = r + s</math>, <math>\phi : \mathbb{F}_2^s \rightarrow \mathbb{F}_2^r</math> is arbitrary and <math>h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2</math> is any Boolean function.

The Walsh transform of <math>f_{\phi,h}</math> takes the value

<math>W_{f_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)}</math>

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

Characterization of Plateaued Functions

Characterization by the Derivatives

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

Let <math>F</math> be an <math>(n,m)</math>-function. Then:

• F is plateuaed if and only if, for every <math>v \in \mathbb{F}_2^m</math>, the size of the set

<math> \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}</math>

does not depend on <math>x</math>;

• F is plateaued with single amplitude if and only if the size of the set depends neither on <math>x</math>, nor on <math>v \in \mathbb{F}_2^m</math> for <math>v \ne 0</math>.

Moreover:

• for every <math>F</math>, the value distribution of <math>D_aD_bF(x)</math> equals that of <math>D_aF(b) + D_aF(x)</math> when <math>(a,b)</math> ranges over <math>(\mathbb{F}_2^n)^2</math>;

• if two plateaued functions <math>F,G</math> have the same distribution, then all of their component functions <math>u \cdot F, u\cdot G</math> have the same amplitude.

Power Functions

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

<math> | \{ (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 \}|.</math>

Then:

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

<math>| \{ (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 \}|;</math>

• <math>F</math> is plateaued with single amplitude if and only if the size above does not, in addition, depend on <math>v \ne 0</math>.

Functions with Unbalanced Components

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

<math> | \{ (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 \}|.</math>

Moreover, <math>F</math> is plateaued with single amplitude if and only if this value does not, in addition, depend on <math>v</math> for <math>v \ne 0</math>.

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 <math>{\rm Im}(D_aF)</math> of any derivative of a strongly-plateaued function <math>F</math> is an affine space.

Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean function <math>f</math> is defined as <math>{\Delta_f}(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + f(x+a)}</math>.

An <math>n</math>-variable Boolean function <math>f</math> is plateaued if and only if, for every <math>x \in \mathbb{F}_2^n</math>, we have

<math>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).</math>

An <math>(n,m)</math>-function <math>F</math> is plateaued if and only if, for every <math>x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m</math>, we have

<math> 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).</math>

Furthermore, <math>F</math> is plateaued with single amplitude if and only if, for every <math>x \in \mathbb{F}_2^n, u \in \mathbb{F}_2^m</math>, we have

<math> \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).</math>

Alternatively, <math>F</math> is plateuaed if and only if, for every <math>x,v \in \mathbb{F}_2^n</math>, we have

<math> 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 \}|.</math>