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.

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