# Difference between revisions of "Plateaued Functions"

Line 106: | Line 106: | ||

<div><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></div> | <div><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></div> | ||

+ | |||

+ | == Characterization by the Means of the Power Moments of the Walsh Transform == | ||

+ | |||

+ | === First Characterization === | ||

+ | |||

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

+ | |||

+ | <div><math>\sum_{w \in \mathbb{F}_2^n} W_f(w + \alpha) W_f^3(w) = 0.</math></div> | ||

+ | |||

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

+ | |||

+ | <div><math>\sum_{w \in \mathbb{F}_2^n} W_F(w + \alpha, u) W_F^3(w,u) = 0.</math></div> | ||

+ | |||

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

+ | |||

+ | === Second Characterization === | ||

+ | |||

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

+ | |||

+ | <div><math> \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></div> | ||

+ | |||

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

+ | |||

+ | <div><math> \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></div> | ||

+ | |||

+ | Moreover, <math>F</math> is plateaued with single amplitude if and only if the two sums above do not depend on <math>u</math> for <math>u \ne 0</math>. | ||

+ | |||

+ | === Third Characterization === | ||

+ | |||

+ | Any Boolean function <math>f</math> in <math>n</math> variables satisfies | ||

+ | |||

+ | <div><math> \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></div> | ||

+ | |||

+ | with equality if and only if <math>f</math> is plateuaed. | ||

+ | |||

+ | Any <math>(n,m)</math>-function <math>F</math> satisfies | ||

+ | |||

+ | <div><math> \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></div> | ||

+ | |||

+ | with equality if and only if <math>F</math> is plateuaed. | ||

+ | |||

+ | In addition, every <math>(n,m)</math>-function satisfies | ||

+ | |||

+ | <div><math>\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></div> | ||

+ | |||

+ | with equality if and only if <math>F</math> is plateuaed. |

## Revision as of 16:28, 8 February 2019

## Contents

# Background and Definition

A Boolean function is said to be *plateaued* if its Walsh transform takes at most three distinct values, viz. 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 **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u \ne 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 does not depend on , or, equivalently, the size of the set does not depend on **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x}**
.

## 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 of the form

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_{\phi,h}(x,y) = x \cdot \phi(y) + h(y)}**

for **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s}**
, where **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r}**
and are any positive integers, , is arbitrary and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle h : \mathbb{F}_2^s \rightarrow \mathbb{F}_2}**
is any Boolean function.

The Walsh transform of takes the value

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W_{f_{\phi,h}}(a,b) = 2^r \sum_{y \in \phi^{-1}(a)} (-1)^{b \cdot y + h(y)}}**

at **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,b)}**
. If **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi}**
is injective, resp. takes each value in its image set two times, then **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_{\phi,h}}**
is plateaued of amplitude **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^r}**
, resp. **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{r+1}}**
.

# Characterization of Plateaued Functions ^{[2]}

## Characterization by the Derivatives

Using the fact that a Boolean function **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f}**
is plateaued if and only if the expression **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{a,b \in \mathbb{F}_2^n} (-1)^{DaDbf(x)}}**
does not depend on **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{F}_2^n}**
, one can derive the following characterization.

Let be an -function. Then:

- F is plateuaed if and only if, for every
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v \in \mathbb{F}_2^m}**, the size of the set

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ (a,b) \in (\mathbb{F}_2^n)^2 : D_aD_bF(x) = v \}}**

does not depend on **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x}**
;

- F is plateaued with single amplitude if and only if the size of the set depends neither on , nor on
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v \in \mathbb{F}_2^m}**for**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v \ne 0}**.

Moreover:

- for every , the value distribution of
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D_aD_bF(x)}**equals that of when ranges over ;

- if two plateaued functions have the same distribution, then all of their component functions have the same amplitude.

### Power Functions

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

Then:

- is plateaued if and only if, for every , we have

- is plateaued with single amplitude if and only if the size above does not, in addition, depend on .

### Functions with Unbalanced Components

Let be an -function. Then is plateuaed with all components unbalanced if and only if, for every , we have

Moreover, is plateaued with single amplitude if and only if this value does not, in addition, depend on for .

### 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 of any derivative of a strongly-plateaued function is an affine space.

## Characterization by the Auto-Correlation Functions

Recall that the autocorrelation function of a Boolean function is defined as .

An -variable Boolean function is plateaued if and only if, for every , we have

An -function is plateaued if and only if, for every , we have

Furthermore, is plateaued with single amplitude if and only if, for every , we have

Alternatively, is plateuaed if and only if, for every , we have

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

### First Characterization

A Boolean function is plateuaed if and only if, for every , we have

An -function is plateuaed if and only if for every and , we have

Furthermore, is plateaued with single amplitude if and only if, in addition, the sum does not depend on for .

### Second Characterization

A Boolean function is plateuaed if and only if, for every , we have

An -function is plateuaed if and only if, for every and every , we have

Moreover, is plateaued with single amplitude if and only if the two sums above do not depend on for .

### Third Characterization

Any Boolean function in variables satisfies

with equality if and only if is plateuaed.

Any -function satisfies

with equality if and only if is plateuaed.

In addition, every -function satisfies

with equality if and only if is plateuaed.