Plateaued Functions

Background and Definition

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

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

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

[math]\displaystyle{ f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y) }[/math]

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

The Walsh transform of [math]\displaystyle{ f_{\phi,h} }[/math] takes the value

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

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

Characterization of Plateaued Functions

Characterization by the Derivatives

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

Let [math]\displaystyle{ F }[/math] be an [math]\displaystyle{ (n,m) }[/math]-function. Then:

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

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

does not depend on [math]\displaystyle{ x }[/math];

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

Moreover:

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

• if two plateaued functions [math]\displaystyle{ F,G }[/math] have the same distribution, then all of their component functions [math]\displaystyle{ u \cdot F, u\cdot G }[/math] have the same amplitude.

Power Functions

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

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

Then:

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

[math]\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 \}|; }[/math]

• [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if the size above does not, in addition, depend on [math]\displaystyle{ v \ne 0 }[/math].

Functions with Unbalanced Components

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

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

Moreover, [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if this value does not, in addition, depend on [math]\displaystyle{ v }[/math] for [math]\displaystyle{ 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]\displaystyle{ {\rm Im}(D_aF) }[/math] of any derivative of a strongly-plateaued function [math]\displaystyle{ F }[/math] is an affine space.

Characterization by the Auto-Correlation Functions

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

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

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

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

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

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

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

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

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

Characterization by the Means of the Power Moments of the Walsh Transform

First Characterization

A Boolean function [math]\displaystyle{ f : \mathbb{F}_{2^n} \rightarrow \mathbb{F}_2 }[/math] is plateuaed if and only if, for every [math]\displaystyle{ 0 \ne \alpha \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0. }[/math]

An [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] is plateuaed if and only if for every [math]\displaystyle{ u \in \mathbb{F}_2^m }[/math] and [math]\displaystyle{ 0 \ne \alpha \in \mathbb{F}_2^n }[/math], we have

[math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0. }[/math]

Furthermore, [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if, in addition, the sum [math]\displaystyle{ \sum_{w \in \mathbb{F}_2^n} W_F^4(w,u) }[/math] does not depend on [math]\displaystyle{ u }[/math] for [math]\displaystyle{ u \ne 0 }[/math].

Second Characterization

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

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

An [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] is plateuaed if and only if, for every [math]\displaystyle{ b \in \mathbb{F}_2^n }[/math] and every [math]\displaystyle{ u \in \mathbb{F}_m }[/math], we have

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

Moreover, [math]\displaystyle{ F }[/math] is plateaued with single amplitude if and only if the two sums above do not depend on [math]\displaystyle{ u }[/math] for [math]\displaystyle{ u \ne 0 }[/math].

Third Characterization

Any Boolean function [math]\displaystyle{ f }[/math] in [math]\displaystyle{ n }[/math] variables satisfies

[math]\displaystyle{ \left( \sum_{a \in \mathbb{F}_2^n} W_f^4(a) \right)^2 \le 2^{2n} \left( \sum_{a \in \mathbb{F}_2^n} W_f^6(a) \right), }[/math]

with equality if and only if [math]\displaystyle{ f }[/math] is plateuaed.

Any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \right)^2 \le 2^{2n} \sum_{u \in \mathbb{F}_2^m} \left( \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) \right), }[/math]

with equality if and only if [math]\displaystyle{ F }[/math] is plateuaed.

In addition, every [math]\displaystyle{ (n,m) }[/math]-function satisfies

[math]\displaystyle{ \sum_{u \in \mathbb{F}_2^m} \sum_{a \in \mathbb{F}_2^n} W_F^4(a,u) \le 2^n \sum_{u \in \mathbb{F}_2^m} \sqrt{ \sum_{a \in \mathbb{F}_2^n} W_F^6(a,u) }, }[/math]

with equality if and only if [math]\displaystyle{ F }[/math] is plateuaed.